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