# Given an integer, how can I detect the nearest integer perfect power efficiently?

If you give me an integer N, how can I detect the nearest integer perfect power, larger or smaller than N?

In other words, the perfect power the distance between N and which is less than the distance between N and any other perfect power. Exponents of 1 are excluded. Prime or composite powers are ok.

This is not a homework question. Is there a method that is better than some kind of neighborhood door knock method? 'Hello, are you a perfect power? No, okay.'

-
Or better than "Which of my n-th roots is closest to an integer?" – DJohnM Feb 8 '13 at 16:19
Exactly. Although @User58220 I think that would be optimal. I mean it is exactly O(log2 N) time, unless the nth root operation takes longer than this. So actually testing the deltas of the log2 N kth roots for k in 2 to log2 N. – Cris Stringfellow Feb 9 '13 at 16:57
For what it's worth, Catalan's Conjecture (now proved) says that $x^y-a^b=1\iff (x,y,a,b)=(3,2,2,3)$ given that $x,y,a,b>1$ so that there are no perfect powers away from each other by more than $1$ (except for $3^2$ and $2^3$). – user26486 Feb 28 '15 at 12:50