MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## how to quickly determine whether a given natural number is a power of any other natural number?

We have a natural number $n>1$. We want to determine whether exists any natural numbers $a, k>1$ such that $n = a^k$.

-
Naive answer: approximate the logarithm to about the same number of places as digits in n (there exist algorithms polynomial time in the number of digits), then check if kth roots are integers for k < log n. Each step takes polynomial time, so the the algorithm terminates in polynomial time. – S. Carnahan Feb 2 2010 at 18:12
springerlink.com/content/km232t5l37357024 – Dan Petersen Feb 2 2010 at 18:18
Simply compute $n^{1/k}$ for $k=2,\ldots,\lfloor \log_2 n \rfloor$. Arbitrary roots can be computed in polynomial time (directly or by using logarithms, as Scott Carnahan said), so this is a polynomial-time algorithm. – Darsh Ranjan Feb 2 2010 at 18:26
I am ignorant in CS .. so this may be a dumb question. Expressing a number to the base p is not a polynomial time problem? – Anweshi Feb 2 2010 at 18:56
Oops, sorry, then one would need to determine the prime factors of a number too.. Which complicates the issue. Anyway I am totally ignorant of this type of things, as I said. – Anweshi Feb 2 2010 at 19:34

This can be done in "essentially linear time." Check out Daniel Bernstein's website: http://cr.yp.to/arith.html

Especially note his papers labeled [powers] and [powers2].

-

In order to test whether or not a natural number $n$ is a perfect power, we can conduct a binary search of the integers {1,2,...,n} for a number a number $m$ such that $n = m^b$ for some $b>1$. Let $b>1$. If a solution $m$ to $m^b =n$ exists,then it must lie in some interval $[c_i,d_i]$. When $i = 0$ we may take $[c_0,d_0] = [1,n]$. To define $[c_{i+1},d_{i+1}]$, consider $\alpha:= \left\lfloor \frac{(ci+di)}{2}\right\rfloor$. If $\alpha^b = n$ then we’re done. If $\alpha^b > n$, let $[c_{i+1}, d_{i+1}] = [c_i, \alpha]$; otherwise $\alpha^b < n$ and we let $[c_{i+1}, d_{i+1}] = [\alpha, d_i]$. We continue in this manner until $|c_i − d_i| \leq 1$. We then increase the value stored in variable $b$ and start the loop again. Performing this loop for all $b \leq log(n)$ completes the algorithm.

A pseudocode implementation of this algorithm can be found on page 21 of Dietzelbinger's Primality Testing in Polynoial Time. Its complexity is about $O(log^3(n))$.

-

For each $k \le \log n/\log 2$, compute an approximation to the positive real $k$-th root of $n$ using Newton's method to enough precision to check if it is an integer. Alternatively, use $p$-adic roots for a suitable $p$, with Newton turning into Hensel.

-