What better way to check if a number is a perfect power?

What better way to check if a number is a perfect power? Need to write an algorithm to check if $n = a^b$ to $b > 1$. There is a mathematical formula or function to calculate this?

I do not know a or b, i know only n.

• What method are you using? You could check if $\log_b(n)$ is an integer for each $b$. – abiessu Aug 18 '13 at 12:46
• Better than what? – Hagen von Eitzen Aug 18 '13 at 12:50
• I'm not using any method. Do not know how to do. In the specific case, i do not know a or b, i know only n, for this i do not can test a log at first. – Sileno Brito Aug 18 '13 at 13:32
• Performing the smallest possible number of operations – Sileno Brito Aug 18 '13 at 13:35
• @user314: Is there a real need for a "perfect powers" tag? – Asaf Karagila Feb 28 '15 at 12:55

It's easy to see that increasing $b$ decreases $a$ (and vice versa). Since the smallest possible value of $a$ is $a_{\mathrm{min}}=2$, the largest useful value of $b$ to be tested is $b_{\mathrm{max}}=\lfloor\log_2 n\rfloor$. Thus, in order to check if $n$ is a perfect power, you only need to check whether any of its second, third, fourth, ... $b_{\mathrm{max}}$-th roots is an integer. Assuming that your $n$ is (at most) a 64-bit integer, this estimate gives you $b_{\mathrm{max}}<64$, meaning that you wouldn't need to check more than 62 different roots in any case.

There are a few further steps you can take:

• The identity $(a^x)^y = a^{xy}$ tells us that it's sufficient to test only prime values of the exponent; if a number is a perfect power, it's also a perfect power with prime exponent (the base is different, of course). This lowers the number of tested exponents to eighteen.
• The high exponents have very few possible bases they can be applied to without exceeding the $64$-bit range. For example, the exponents greater than $40$ can only correspond to base $2$. Instead of checking them using the "expensive" arithmetic, you can just have the possible values corresponding to these exponents hard-coded into the program and just compare the checked number against them. For example, storing the six values $2^{41}, 2^{43}, \ldots 2^{61}$ can save you checking six possible roots.
• Of course, one doesn't need to stop at base $2$; a few more pre-calculated numbers and the maximum exponent can be lowered even further! For example, $38$ additional numbers can be used to eliminate exponents from $23$ onwards (leaving just eight to be checked) or $144$ (in total) to get down to just the four possible single-digit exponents ($2$, $3$, $5$ and $7$).

Somehow, I can show that the binary search algorithm is $O(lg~n \cdot (lg~lg~n)^2)$.

Firstly, $a^b = n$, there is $b<lg~n$.
Binary Search Algorithm: For each $b$, we use binary search to find $a$.

Each time the computation of $a^b$ cost $lg~b = lg~lg~n$ operations by using fast exponentiation. Therefore, the remaining issue is the range of $a$.

If $A$ is the maximal possible value of $a$, then binary search needs $lg~A$ operations

Note that $b~lg~a = lg~n$, that is $$lg~A = \frac{lg~n}{b}$$ When summing up, $$\sum lg~A = lg~n \cdot (\frac{1}{1} + \frac{1}{2} + ... + \frac{1}{B}) = lg~n \cdot lg~B = lg~n \cdot lg~lg~n$$

In other words, all the operations for binary search is $O(lg~n \cdot lg~lg~n)$

Consider the operation of $a^b$, it is $O(lg~n \cdot (lg~lg~n)^2)$ finally.

ps: All the lg are base 2.

• This does not address the question – Shailesh Jul 2 '16 at 16:18
• Well, if the question is whether a quick formula exists, of cause not (at least nobody found yet). If the question is writing a fast algorithm, here is my answer. And the time complexity is as fast as the current best from another paper DETECTING PERFECT POWERS IN ESSENTIALLY LINEAR TIME – Kevin Jul 9 '16 at 2:07