Algoritma untuk menghitung jarak antara kekuatan

$a, b$

Di sini $x, y$ adalah bilangan bulat. Jelas mengambil $x = y = 0$ memberikan jawaban yang tidak menarik; secara umum seberapa dekat kekuatan ini bisa didapat? Juga, bagaimana kita dengan cepat menghitung diminimalkan $x, y$ ?

Pertama saya pikir akan lebih baik menggunakan fraksi lanjutan dari dan menguji pada konvergennya, karena pada konvergen itu ada titik dalam beberapa hal pendekatan yang optimal. Setelah itu menjadi jelas, bahwa orang perlu menggunakan setidaknya fraksi lanjutan umum untuk memastikan memiliki jarak yang menurun monoton. Setelah itu dan algoritma yang rumit dengan ini, brute-force algo berikut bahkan lebih cepat di Pari / GP( x , y $\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 
       );
   )); }

setelah panggilan itu mylist(100,1000,3,3,100)untuk menemukan semua perbedaan kecil dengan mana kedua eksponen setidaknya untuk semua pangkalan dan . Periksa hanya hingga dan . 3 a = 2..100 b = ( a + 1 ) . . 1000 maks ( X ) = 30 maks ( y ) = $|d| \lt 100$$3$$a=2..100$$b=(a+1) .. 1000$$\max (X)=30$$\max(y)=20$

Ini jauh lebih cepat daripada pendekatan fraksi berkelanjutan (yang juga memiliki lebih banyak masalah tidak baik (misalnya dengan kelengkapan solusi) yang sulit untuk ditangani) meskipun itu entah bagaimana cara yang naif ...

Protokol (dipesan secara manual):

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