10
$\begingroup$

Given coprime $a, b$, can you quickly compute $$ \min_{x, y > 0} |a^x - b^y| $$

Here $x, y$ are integers. Obviously taking $x = y = 0$ gives an uninteresting answer; in general how close can these powers get? Also, how do we quickly compute the minimizing $x, y$?

Improve this question
$\endgroup$
3
  • 7
    $\begingroup$ Do you know that that's even computable? ​ ​ $\endgroup$
    – user6973
    Commented Oct 20, 2017 at 20:27
  • 1
    $\begingroup$ If you fix $x$, it's easy to show that, for the minimizer, $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\}$. That reduces it to a one-dimensional search. $\endgroup$
    – Thomas Steinke
    Commented Oct 20, 2017 at 20:52
  • 5
    $\begingroup$ Please don't simultaneously cross-post, or at least link to the other post(s). mathoverflow.net/questions/283903/… $\endgroup$
    – usul
    Commented Oct 21, 2017 at 0:47

1 Answer 1

Reset to default
-2
$\begingroup$

First I thought it would be best to use the continued fraction of $\log(a)/\log(b)$ and test at its convergents, because at that convergents there are points $(x,y)$ of in some sense optimal approximation. After that it becomes clear, that one needs to use at least the generalized continued fractions to make sure to have monotonic decreasing distances.
After that and the complicated algorithm with this the following brute-force algo was even faster in 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 
       );
   )); }

after that call mylist(100,1000,3,3,100) to find all small difference with $|d| \lt 100$ where both exponents are at least $3$ for all bases $a=2..100$ and $b=(a+1) .. 1000$ . Check only up to $\max (X)=30$ and $\max(y)=20$.

This was much faster than the continued-fraction approach (which also had more unkind issues (for instance with completeness of the solutions) which are difficult to handle) although it is a somehow naive algo ...

A protocol (manually ordered) : 

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
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.