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.

Solutions Collecting From Web of "What better way to check if a number is a perfect power?"

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.