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.'
 A: One algorithm is as follows.  You know that the exponent will be at least $2$, so you won't have to take powers greater than $\log_2 N$.  So loop over $k = 2, 3, \ldots, \lfloor \log_2 N \rfloor$; for each one examine the candidates $\lfloor N^{1/k} \rfloor^k$ and $\lceil N^{1/k} \rceil^k$.  This finds perfect squares, cubes, 4th powers, ... near $N$.  This is the algorithm
Another algorithm, obviously worse, is to find perfect powers of $2, 3, \ldots, \sqrt{N}$ near $N$.  Loop over $j = 2, 3, \ldots, \sqrt{N}$, and for each one examine the candidates $j^{\lfloor x \rfloor}$ and $j^{\lceil x \rceil}$ where $x = \log_j N$.
You can improve by combining the two.  Run the first algorithm for $k = 2, 3, \ldots, f(N)$, which will find cases where the exponent is small, at most $f(N)$. Then run the second for $j = 2, 3, \ldots, g(N)$, which will find cases where the exponent is large, at least $(\log N)/(\log g(N))$.  So you need to test twice $f(N) + g(N)$ candidates; you want to minimize $f(N) + g(N)$ subject to $f(N) > (\log N)/(\log g(N))$, i. e. $g(N)^{f(N)} > N$.  
For example if $N = 10^{100}$ you can compute (I don't know a good way to do this other than trial and error) that $f(N) = 21$, since $21^{76} > 10^{100}$, is optimal.  So loop over $k = 2, 3, \ldots, 21$ and find the nearest $k$th powers; then loop over $j = 2, 3, \ldots, 76$ to find the nearest powers of $2, 3, \ldots, 76$.  This only requires checking $2 \times (21 + 76 - 2) = 190$ candidates, compared to $2 \times 331 = 662$ for just using my first algorithm.
A: The following function , written in PARI/GP does the job very efficiently :
power(n)={mini=n;for(s=2,ceil(log(n)/log(2))+1,m=round(n^(1/s));if(abs(m^s-n)<mini,mini=abs(m^s-n);[a,b]=[m,s]));[a,b]}

The routine works for $n\ge 3$, for very large $n$ you need to increase the realprecision. In most cases, the program just outputs the nearest square , which is typically the optimal result.
