Dado el coprimo , ¿puede calcular rápidamente
Aquí son enteros. Obviamente, tomar da una respuesta poco interesante; en general, ¿qué tan cerca pueden llegar estos poderes? Además, ¿cómo calculamos rápidamente la minimización de ?
Dado el coprimo , ¿puede calcular rápidamente
Aquí son enteros. Obviamente, tomar da una respuesta poco interesante; en general, ¿qué tan cerca pueden llegar estos poderes? Además, ¿cómo calculamos rápidamente la minimización de ?
Respuestas:
Primero pensé que sería mejor usar la fracción continua de y probar en sus convergentes, porque en esos convergentes hay puntos de alguna aproximación óptima en cierto sentido. Después de eso queda claro, que uno necesita usar al menos las fracciones continuas generalizadas para asegurarse de tener distancias monotónicas decrecientes. Después de eso y el complicado algoritmo con esto, el siguiente algoritmo de fuerza bruta fue aún más rápido en Pari / GPIniciar sesión( a ) / log( b ) ( x , y)
después de esa llamadaEl | reEl | <100 3 a = 2..100 b = ( a + 1 ) . . 1000 max ( X) = 30 max ( y) = 20
mylist(100,1000,3,3,100)
para encontrar todas las pequeñas diferencias con donde ambos exponentes son al menos para todas las bases y . Marque solo hasta y .Esto fue mucho más rápido que el enfoque de fracción continua (que también tenía más problemas desagradables (por ejemplo, con la integridad de las soluciones) que son difíciles de manejar) aunque es algo algo ingenuo ...
Un protocolo (ordenado manualmente):
fuente