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

```


---

