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.
 A: 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$).

A: 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.
