<p>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 <strong><em>generalized</em></strong> continued fractions to make sure to have monotonic decreasing distances.<br>
After that and the complicated algorithm with this the following brute-force algo was even faster in Pari/GP </p>

<pre><code>\\ print X,Y,d conditional X&gt;lowboundX, Y &gt; lowboundY, d&lt;upperboundD
{pri1(lbX,lbY,ubd,a,b,X,Y,d)=if(X&lt;lbX || Y&lt;lbY || abs(d)&gt;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)&gt;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&lt;0,Xa*=a;d=Xa-Yb;X++;pri1(lbX,lbY,ubd,a,b,X,Y,d););
        while(d&gt;0,Nb*=b;d=Xa-Yb;Y++;pri1(lbX,lbY,ubd,a,b,X,Y,d););
        if(X&gt;30 || Y&gt;20, break());  \\ stop at max X=30 or Y=20 
       );
   )); }
</code></pre>

<p>after that call <code>mylist(100,1000,3,3,100)</code> 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$.      </p>

<p>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 ...       </p>

<p>A protocol (manually ordered) :   </p>

<pre><code>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
</code></pre>

CC BY-SA 3.0
2017-10-21T14:14:21.850Z
2017-10-21T14:24:59.777Z
2017-10-21T14:24:59.777Z
Gottfried Helms
<p>Given coprime $a, b$, can you quickly compute $$ \min_{x, y &gt; 0} |a^x - b^y| $$</p>

<p>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$?</p>

CC BY-SA 3.0
2017-10-20T20:52:10.960Z
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.
Thomas Steinke
CC BY-SA 3.0
2017-10-21T00:47:20.903Z
Please don't simultaneously cross-post, or at least link to the other post(s). https://mathoverflow.net/questions/283903/how-close-can-powers-of-coprime-integers-get
usul
<ds.algorithms><randomized-algorithms><nt.number-theory><comp-number-theory>
Algorithm to compute distance between powers
Gautam
# Algorithm to compute distance between powers

(Asked by: username_0 on 2017-10-20)

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$?

**Tags:** ds.algorithms, randomized-algorithms, nt.number-theory, comp-number-theory
> **Comments:**
> **username_1**: 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.  
> **username_2**: Please don't simultaneously cross-post, or at least link to the other post(s). https://mathoverflow.net/questions/283903/how-close-can-powers-of-coprime-integers-get  

---

## 1 answers

### Answer by username_3 on 2017-10-21. Score: -2

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, dubd,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


---

