Considere un cierto número racional y deja ser un entero positivo. ¿Hay alguna manera de encontrar la mejor aproximación racional? de entre todas las fracciones tales que con no necesariamente coprime? Tengo una idea intuitiva, pero esto no es realmente útil si es grande y ni siquiera estoy seguro de que funcione correctamente en general.
Explico esta idea con un ejemplo concreto.
Suponer y deja La condición “exacta” significa que existe un entero tal que Usando Encuentro que la condición exacta se realiza cuando Entonces Si quiero una mejor aproximación con mi restricción, debería obtener el divisor más cercano de a de arriba y de abajo, que son y Las aproximaciones correspondientes son y y de una comprobación fácil vemos que es la mejor aproximación.
Esta estrategia puede tener un gran problema cuando es enorme: en particular cuando se desconoce su factorización o cuando tiene muchos divisores. ¿Hay alguna manera de tratar este problema con bastante facilidad? Sé que hay algunas estrategias que usan el truncamiento de las fracciones continuas, pero la restricción en el producto parece no ser buena para ser tratada de esta manera.
Por ejemplo, ¿cómo puedo resolver el problema cuando y ?
. . . Entonces queremos un divisor de cerca de .
. Tomando registros, queremos con , , ..., . Este es un problema de programación entera. Existen técnicas eficientes para encontrar soluciones (pero no las conozco lo suficientemente bien como para entrar en detalles). Ciertamente, hay algoritmos de búsqueda de relaciones enteras como PSLQ que podrían aplicarse. Consulte, para empezar, https://en.wikipedia.org/wiki/Integer_relation_algorithm