How close can powers of coprime integers get? Given coprime $a, b$, what is $$ \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$?
 A: Gerhard says what needs to be said: Try $y=1$ and in very rare case $y=2$ or maybe $3.$
Here is an exceptional example: $1138^2-109^3=15.$ 
You didn't ask for exceptional cases, just what to do given $a$ and $b.$ 
For that, find rational numbers $\frac{x}{y}$ which approximate $\frac{\ln{b}}{\ln{a}}$ well. The first few convergents to $\frac{\ln{1138}}{\ln{109
}}$ are $2, \frac{3}{2}, \frac{607547}{405031}.$ The huge jump suggests that it is worth checking $3,2.$
I don't see any reason to assume that $a$ and $b$ are relatively prime.
LATER Inspired by @Gerry let me observe this: Let $a=2$ and $b=\lfloor 2^k \sqrt{2}\rceil.$ Then $b^1-2^k \approx 2^k(\sqrt{2}-1)$ while $|b^2-2^{2k+1}| \lt 2^k \sqrt{2}.$ This suggests to me that with probability about $1-\frac1{\sqrt2} \approx0.3$ it will happen that $|b^2-2^{2k+1}| \lt b-2^k.$ This does happen $26$ times up to $2k+1=201.$  The first and last few are $2k+1=15, 17, 19, 31, 33, 59, \cdots 147, 149, 161, 187, 193.$ I can see why this might even more successful for odd powers $m^{2k+1}$ of larger
  integers.
A: You can get a conjectural lower bound for $|a^x-b^y|$ using the $ABC$-conjecture. I'll do the case $a^x > b^y$ for simplicity. Taking $A=a^x$, $B=-b^y$, and $C=a^x-b^y$, we get for every $\epsilon >0$ that there is a $K=K_\epsilon>0$ so that
$$
a^x \le K\prod_{p\mid ab(a^x-b^y)} p^{1+\epsilon}
\le K(ab(a^x-b^y))^{1+\epsilon}.
$$
Replacing $K$ with a $K'=K'_\epsilon$, this gives
$$
a^x - b^y \ge K' \left(\frac{a^{x-1}}{b}\right)^{1-\epsilon}.
$$
This shows that if $x$ and $y$ are large, you can't make $a^x-b^y$ very much smaller than $a^x$. (You can also prove an effective lower bound using linear forms in logs, but it will be much weaker than this.)
A: If one looks at the sequence of perfect powers (1,4,8,9,16,25,27,32,36,... found at OEIS at https:/oeis.org/A001597 ), one sees a lot of squares.  If one wants to tackle the posted question by looking at this sequence, one can save time looking at odd powers. Note that all pairs listed by Gottfried Helms have one even exponent and one odd exponent.
Indeed, since (a^2 - b^2)=(a-b)(a+b), interesting answers to the question will involve an odd exponent, usually coprime to the other exponent.  More specifically, interesting answers will be odd powers near a square, and two distinct odd powers which lie between two squares.  Thus, an algorithm which looks only at odd powers which are not squares , and just the squares adjacent to them, saves time by looking at just the interesting cases. Further to avoid answers producing zero (like 225 and 3375), we look only at pairs which give distinct powers.
I generated the first two million cubes, as well as the smattering of higher powers (excepting two or three really large powers of 2 or 3 with the exponent prime) occurring between these cubes.  I got less than 100 cases  where these powers were within 100 of a square.  I counted 14 cases where two odd powers had no squares between them , and 32 where there was only one square.  The largest number less than 10^18 that was a perfect power and was within 100 of a square was 8158^3 which is 24 less than a square.  The other slightly over 4 million differences I computed were over 1000 or were small known examples of near powers less than  10000, e.g. 2187,2197,2209.  This suggests to me to look for powers that are within s^{1/3} of a square s.
Gerhard "Is Feeling Rather Powerfull Presently" Paseman, 2017.10.23.
