Algoritmo para calcular a distância entre potências

$a, b$

min_{x, y > 0} | a^{x} - b^{y} |

$\min_{x, y > 0} |a^x - b^y|$

Aqui são inteiros. Obviamente, tomar dá uma resposta desinteressante; em geral, quão próximos esses poderes podem chegar? Além disso, como calculamos rapidamente o minimizador ? $x, y$ $x = y = 0$ $x, y$

ds.algorithms randomized-algorithms nt.number-theory comp-number-theory Gautam
fonte

Você sabia que isso é computável?

Se você corrigir , é fácil mostrar que, para o minimizador, . Isso reduz a uma pesquisa unidimensional.

x

$x$

y \in {⌊ x \cdot \frac{\log a}{\log b} ⌋, ⌈ x \cdot \frac{\log a}{\log b} ⌉}

$y \in \left\{ \left\lfloor x \cdot \frac{\log a}{\log b} \right\rfloor , \left\lceil x \cdot \frac{\log a}{\log b} \right\rceil \right\}$

Thomas

Não faça postagens cruzadas simultaneamente ou, pelo menos, faça o link para as outras postagens. mathoverflow.net/questions/283903/...

usul

Primeiro, pensei que seria melhor usar a fração contínua de e testar seus convergentes, porque nesses convergentes existem pontos de alguma forma, aproximação ideal. Depois disso, fica claro que é necessário usar pelo menos as frações contínuas generalizadas para garantir distâncias monotônicas decrescentes. Depois disso e o complicado algoritmo com isso, o seguinte algo de força bruta foi ainda mais rápido em Pari / GP $\log(a)/\log(b)$ $(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 
       );
   )); }

depois dessa chamada mylist(100,1000,3,3,100)para encontrar todas as pequenas diferenças com , onde ambos os expoentes são, pelo menos, para todas as bases de e . Verifique apenas até e . $|d| \lt 100$ $3$ $a=2..100$ $b=(a+1) .. 1000$ $\max (X)=30$ $\max(y)=20$

Isso foi muito mais rápido do que a abordagem de fração contínua (que também teve mais problemas desagradáveis (por exemplo, com integridade das soluções) que são difíceis de manusear), embora seja algo de alguma maneira ingênuo ...

Um protocolo (pedido 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

Elmos de Gottfried
fonte

Algoritmo para calcular a distância entre potências

Respostas: