how to quickly determine whether a given natural number is a power of any other natural number? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T10:35:51Z http://mathoverflow.net/feeds/question/13843 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/13843/how-to-quickly-determine-whether-a-given-natural-number-is-a-power-of-any-other-n how to quickly determine whether a given natural number is a power of any other natural number? Oleg 2010-02-02T18:06:08Z 2010-02-02T19:03:04Z <p>We have a natural number $n>1$. We want to determine whether exists any natural numbers $a, k>1$ such that $n = a^k$. </p> <p>Please suggest a polynomial-time algorithm.</p> http://mathoverflow.net/questions/13843/how-to-quickly-determine-whether-a-given-natural-number-is-a-power-of-any-other-n/13845#13845 Answer by Felipe Voloch for how to quickly determine whether a given natural number is a power of any other natural number? Felipe Voloch 2010-02-02T18:26:17Z 2010-02-02T18:26:17Z <p>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.</p> http://mathoverflow.net/questions/13843/how-to-quickly-determine-whether-a-given-natural-number-is-a-power-of-any-other-n/13849#13849 Answer by Ben Linowitz for how to quickly determine whether a given natural number is a power of any other natural number? Ben Linowitz 2010-02-02T18:40:06Z 2010-02-02T18:40:06Z <p>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 &lt; 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. </p> <p>A pseudocode implementation of this algorithm can be found on page 21 of Dietzelbinger's <a href="http://books.google.com/books?id=DWdjlaxl_7YC&amp;dq=primality+testing+in+polynomial+time&amp;printsec=frontcover&amp;source=bn&amp;hl=en&amp;ei=HnFoS4XxEMuXtgf21KXUBg&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=4&amp;ved=0CB4Q6AEwAw#v=onepage&amp;q=&amp;f=false" rel="nofollow">Primality Testing in Polynoial Time</a>. Its complexity is about $O(log^3(n))$.</p> http://mathoverflow.net/questions/13843/how-to-quickly-determine-whether-a-given-natural-number-is-a-power-of-any-other-n/13852#13852 Answer by Pace Nielsen for how to quickly determine whether a given natural number is a power of any other natural number? Pace Nielsen 2010-02-02T19:03:04Z 2010-02-02T19:03:04Z <p>This can be done in "essentially linear time." Check out Daniel Bernstein's website: <a href="http://cr.yp.to/arith.html" rel="nofollow">http://cr.yp.to/arith.html</a></p> <p>Especially note his papers labeled [powers] and [powers2].</p>