Алгоритм вычисления расстояния между степенями

9

Данный взаимный a,bМожете ли вы быстро вычислить

minx,y>0|axby|

Вот x,yцелые числа. Очевидно, принимаяx=y=0дает неинтересный ответ; в общем, насколько близки эти силы? Кроме того, как мы можем быстро вычислить минимизациюx,y?

Гаутама
источник
6
Вы знаете, что это даже вычислимо?
1
Если вы исправите xлегко показать, что для минимизатора y{xlogalogb,xlogalogb}, Это сводит его к одномерному поиску.
Томас
5
Пожалуйста, не кросс-пост, или хотя бы ссылки на другие посты. mathoverflow.net/questions/283903/…
усул

Ответы:

-2

Сначала я подумал, что было бы лучше использовать продолжение доли log(a)/log(b) и проверить на его сходящихся, потому что на этих сходящихся есть точки (x,y)в некотором смысле оптимального приближения. После этого становится ясно, что нужно использовать хотя бы обобщенные цепные дроби, чтобы обеспечить монотонное уменьшение расстояний.
После этого и сложный алгоритм с этим следующий алгоритм перебора был еще быстрее в Pari / GP

\\ 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 
       );
   )); }

после этого звонка, mylist(100,1000,3,3,100)чтобы найти все небольшие различия с|d|<100 где оба показателя по крайней мере 3 для всех баз a=2..100 а также b=(a+1)..1000, Проверьте только доmax(X)=30 а также max(y)=20,

Это было намного быстрее, чем подход с непрерывной дробью (который также имел более недобрые проблемы (например, с полнотой решений), с которыми трудно справиться), хотя это несколько наивный алгоритм ...

Протокол (заказывается вручную):

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
Готфрид Хелмс
источник