Encontrar soluciones de números enteros a una desigualdad doble

Question

Estoy buscando un método rápido para encontrar un $(x, y)$ solución entera de una desigualdad doble.

Dado un A entre $0$ y $1$ :

$$ {y \over x^2} < A < {y \over x^2 - 1} $$

---

Por ejemplo A = 0.017 la primera solución que encuentro es (106, 191) y sólo por fuerza bruta... tratando de $$x = [2, +\infty] \\ y = [1, x]$$

---

Cualquier idea será muy apreciada.

También pido disculpas por la terminología matemática deficiente que he utilizado.

Answer 1

Dado que la pregunta deja varias cuestiones sin resolver, como 1) qué significa rápido (excepto que no es fuerza bruta), 2) qué son los valores de A, 3) cómo de precisos son los valores de A (¿con tres decimales?), y 4) si estás haciendo esto manualmente o escribiendo un programa, esta respuesta puede, en el mejor de los casos, ayudar (pero no es necesariamente una solución).

Para utilizar el ejemplo, desea valores de $17x^2\;mod\;1000$ que son pequeños. En el caso de $106$ el valor de esa expresión es $12$ . Para todos los valores de $8 \leq x < 106$ el valor es como mínimo $33$ .

Cuando encuentre un valor de $x$ donde el valor de la expresión es pequeño, se puede ver si satisface las desigualdades ( $y$ será $floor(Ax^2)$ ). Así que todavía estás forzando $x$ pero te estás saltando el cálculo de $y$ y las desigualdades para la mayoría de los casos.

Para optimizar aún más, puede omitir algunos valores a la vez. Por ejemplo, digamos que está iterando a través de $x$ y actualmente es $40$ . El resto será $200$ (en el ejemplo). El resto de la diferencia $41$ y $42$ será $((41+42)*17\;mod\;1000) = 377$ . El resto de la diferencia entre $42$ y $43$ será $377+2*17=411$ . Desde $200+377+411 < 1000$ puede omitir la comprobación $x=41,42$ . En otras palabras, podría pasar de $40$ à $43$ .