Algoritmo para calcular la distancia entre potencias

9

Dado el coprimo , ¿puede calcular rápidamentea,b

minx,y>0|axby|

Aquí x,y son enteros. Obviamente, tomar x=y=0 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 x,y ?

Gautama
fuente
66
¿Sabes que eso es incluso computable?
1
Si corrige x , es fácil mostrar que, para el minimizador, y{xlogalogb,xlogalogb} . Eso lo reduce a una búsqueda unidimensional.
Thomas
55
Por favor, no publique mensajes cruzados simultáneamente, o al menos enlace a las otras publicaciones. mathoverflow.net/questions/283903/…
usul

Respuestas:

-2

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(una)/ /Iniciar sesión(si)(X,y)

\\ print X,Y,d conditional X>lowboundX, Y > lowboundY, d<upperboundD
{pri1(lbX,lbY,ubd,a,b,X,Y,d)=if(X<lbX || Y<lbY || abs(d)>ubd,return(0)); 
                  print(a,"^",X,"-",b,"^",Y,"=",d)); }


{mylist(maxa=19,maxb=99,lbX=3,lbY=2,ubd=100)=print(" ");
for(a=2,maxa,for(b=a+1,maxb,
     if(gcd(a,b)>1,next()); \\ ignore trivial multiples
     X=1;Y=1;Xa=a;Yb=b;
     d=Xa-Yb;  pri1(lbX,lbY,ubd,a,b,X,Y,d);
     for(k=1,20, 
        while(d<0,Xa*=a;d=Xa-Yb;X++;pri1(lbX,lbY,ubd,a,b,X,Y,d););
        while(d>0,Nb*=b;d=Xa-Yb;Y++;pri1(lbX,lbY,ubd,a,b,X,Y,d););
        if(X>30 || Y>20, break());  \\ stop at max X=30 or Y=20 
       );
   )); }

después de esa llamada 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 . El |reEl |<1003una=2..100si=(una+1)..1000max(X)=30max(y)=20

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):

gettime();mylist(200,10 000,3,3,100);gettime() /1000.0 \\ ~ a*b/6000 sec
  (400 sec)

 2^8- 3^5= 13

 6^7-23^4= 95
 2^7- 3^4= 47

 2^7- 5^3=  3
 2^5- 3^3=  5
 3^4- 4^3= 17

---------------
 2^6- 3^4=-17

 3^5- 4^4=-13
 2^5- 3^4=-49

 2^8- 7^3=-87
(4^4- 7^3=-87)

 3^7-13^3=-10
 2^6- 5^3=-61
(4^3- 5^3=-61)
 2^5- 5^3=-93

 2^4- 3^3=-11
 3^4- 5^3=-44
 6^4-11^3=-35
15^4-37^3=-28

 3^3- 4^3=-37
 3^3- 5^3=-98
 5^3- 6^3=-91
Yelmos de Gottfried
fuente