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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.