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

Question

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.

Answer 1

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