Algorithmus zur Berechnung des Abstandes zwischen Potenzen

9

Bei gegebener Koprime a,b können Sie schnell berechnen

minx,y>0|axby|

Hier sind x,y ganze Zahlen. Offensichtlich ergibt x=y=0 eine uninteressante Antwort; Wie nahe können diese Kräfte im Allgemeinen kommen? Wie berechnen wir schnell das minimierende x,y ?

Gautam
quelle
6
Wissen Sie, dass das überhaupt berechenbar ist?
1
Wenn Sie x korrigieren x, können Sie leicht zeigen, dass für den Minimierer y{xlogalogb,xlogalogb} . Das reduziert es auf eine eindimensionale Suche.
Thomas
5
Bitte nicht gleichzeitig Cross-Post oder zumindest Link zu den anderen Posts. mathoverflow.net/questions/283903/…
usul

Antworten:

-2

Zuerst dachte ich, es wäre am besten, den fortgesetzten Bruchteil von und an seinen Konvergenzen zu testen, da es an diesen Konvergenzen Punkte in gewissem Sinne eine optimale Annäherung aufweisen. Danach wird klar, dass man mindestens die verallgemeinerten fortgesetzten Brüche verwenden muss, um sicherzustellen, dass monoton abnehmende Abstände vorliegen. Danach und dem damit verbundenen komplizierten Algorithmus war das folgende Brute-Force-Algo in Pari / GP noch schnellerlog(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 
       );
   )); }

nach diesem Aufruf mylist(100,1000,3,3,100), um alle kleinen Unterschiede mit wobei beide Exponenten für alle Basen und mindestens sind . Überprüfen Sie nur bis zu und . |d|<1003a=2..100b=(a+1)..1000max(X)=30max(y)=20

Dies war viel schneller als der Ansatz der fortgesetzten Fraktion (der auch unfreundlichere Probleme hatte (zum Beispiel mit der Vollständigkeit der Lösungen), die schwer zu handhaben sind), obwohl es sich um eine irgendwie naive Algo handelt ...

Ein Protokoll (manuell bestellt):

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
Gottfried Helms
quelle