1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What method are you using? You could check if $\log_b(n)$ is an integer for each $b$. $\endgroup$ – abiessu Aug 18 '13 at 12:46
  • $\begingroup$ Better than what? $\endgroup$ – Hagen von Eitzen Aug 18 '13 at 12:50
  • $\begingroup$ 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. $\endgroup$ – Sileno Brito Aug 18 '13 at 13:32
  • $\begingroup$ Performing the smallest possible number of operations $\endgroup$ – Sileno Brito Aug 18 '13 at 13:35
  • 2
    $\begingroup$ @user314: Is there a real need for a "perfect powers" tag? $\endgroup$ – Asaf Karagila Feb 28 '15 at 12:55
3
$\begingroup$

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$).
$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ This does not address the question $\endgroup$ – Shailesh Jul 2 '16 at 16:18
  • $\begingroup$ 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 $\endgroup$ – Kevin Jul 9 '16 at 2:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.