Contar el número de soluciones enteras para $a \times b \geq k$ ?

Question

Contar el número de soluciones enteras para $a \times b \geq k$

dadas las condiciones

1) $1 \leq a \leq p$

2) $1 \leq b \leq q$

(k, p y q son constantes).

Answer 1

En términos gráficos, estás contando el número de puntos de la red (es decir, puntos con componentes enteros) que están dentro o en el límite del rectángulo con esquinas opuestas $(0, 0)$ y $(p, q)$ y que están por encima o sobre la hipérbola $xy=k$ . Con esto en mente tenemos tres casos:

1. Si $pq < k$ el rectángulo se encuentra por debajo de la hipérbola, por lo que no hay soluciones.

2. Si $pq = k$ sólo la esquina superior derecha del rectángulo intersecará la hipérbola, por lo que habrá una única solución, $a=p, b=q.$

3. Si $pq > k$ hay al menos dos caminos posibles. La más sencilla es obtener un límite superior para el número de soluciones. Ciertamente, el número de soluciones no será mayor que el área por encima de la curva $xy=k,$ por debajo de la línea $y=q,$ y a la izquierda de la línea $x=p$ . La curva y la línea se cruzan cuando $x=k/q$ por lo que el área será

$$ A = \int_{k/q}^p k-\frac{k}{x} dx = pq+k\left(\ln\frac{k}{pq}-1\right) $$

Para la mayoría de los valores de $p$ y $q,$ resulta estar bastante cerca del número real de soluciones.

Por otra parte, si desea una respuesta exacta, puede encontrar el casco convexo de su conjunto de puntos de solución y, a continuación, utilizar Teorema de Pick . Aunque hará lo que quieres, la respuesta no será tan sencilla como la estimación anterior.