# Shortcuts for next perfect power computation

The answers in Given an integer, how can I detect the nearest integer perfect power efficiently? show two effective algorithms for computing the nearest perfect power for a given integer $n$, although they can be improved by checking only prime exponents.

My algorithm for computing the next perfect power $\mathrm{np}(n)$ greater than or equal an integer $n\ge 8$ basically minimizes $d(n,p) = \lceil n^{1/p} \rceil ^p - n$ for all primes $p \le \log_2 n+2.$

If $d(n,p)=0$ (or $\lceil n^{1/p} \rceil =1$) during the prime loop, the required power is obviously found and we are done. But due to Catalan's conjecture (or Mihăilescu's theorem) we can do better and stop if $d(n,p) < 2.$

Since the next perfect power is in most cases $\lceil \sqrt{n} \rceil ^2$, the following question arises:

Are there other shortcuts or conditions to detect $\mathrm{np}(n)=\lceil \sqrt{n} \rceil ^2$ without computing $d(n,p)$ for primes $p>2?$ Are there more Mihăilescu type shortcuts?

• this is the limit $O(\ln n)$ , i don't think you could improve this any further. – Ahmad Sep 11 '17 at 12:23