# How does one find out whether $N = a^b$ for some $b$?

I was trying to find out how to find whether $N$ is a perfect power or not for some $a$ and $b$ (so the algorithm should discover that its not a perfect power if its not expressable in the form $a^b$).

My intuition tells me that for every value of the exponent $b$ we can binary search $a$ in the set $\{ 1,...,N-1 \}$. However, what I am not convinced yet is that this algorithm won't run forever, i.e. that we won't try new values of $b$ forever. Also, if someone has any comments on the correctness of the algorithm I suggested it would be greatly appreciated.

• How about finding the prime factorisation as a first step? – greybeard Oct 8 '15 at 17:23
• – Charlie Parker Oct 8 '15 at 23:30
• (finding the prime factorisation seems to be slow intolerably slow, as detecting perfect powers is a first step in a fast primality test. That said, I have no idea about the operations considered to take unit time in algorithms using transcendental functions.) – greybeard Oct 9 '15 at 13:15
• cs.stackexchange.com/q/26379/755 – D.W. Apr 10 at 4:32

Yes, your approach is a good one. The only thing you missed is that there's a simple upper bound $b \le \lg N$.

Do you see why? It's easier to see why if you state more carefully the problem you are trying to solve. You are asking whether there exist $a,b \in \mathbb{N}$ such that $a \ge 2$, $b \ge 2$, and $a^b=N$. Taking logs of both sides, we get $b \lg a = \lg N$. From the fact that $a \ge 2$, we see $\lg a \ge 1$, so $b = (\lg N)/(\lg a) \le \lg N$.

Therefore, here is a simple algorithm:

• For $b=2,3,\dots,\lg N$:

• Use binary search to search for $a \in \mathbb{N}$ such that $a^b=N$.

Each iteration of the loop will take $O(\lg N)$ time (the time for a binary search over at most $N$ possibilities), and you do $\lg N$ iterations of the loop, so the total running time $O((\lg N)^2)$.

In particular, yes, this will always terminate. You don't need to keep trying new values for $b$ forever, since we know that $b$ is an integer and is no larger than $\lg N$.

The running time of the algorithm can be improved a bit by replacing the binary search with a faster algorithm to compute $\sqrt[b]{N}$; for instance, you could use Newton's method. But the basic method above is already very efficient.

You might be tempted to iterate over all possible values of $a$, and then do a binary search for $b$. Don't do that; there are $\Theta(\sqrt{N})$ possible values of $a$, so this will be unavoidably slow.

Instead, a better approach is to iterate over all possible values of $b$, and then do a binary search for a matching $a$. This is much faster, as it needs only $\Theta(\lg N)$ binary searches rather than $\Theta(\sqrt{N})$ of them.

One person mentioned factoring $N$. This is much slower. Our best algorithms for factoring run in subexponential time; they are much slower than the $\Theta((\lg N)^2)$ running time of the algorithm above.

In addition to what @templatetypedef described, assuming we are talking about natural numbers, $a > 1$, and $b > 1$ we can make the following considerations:

• The greatest number $a$ we have to consider is $sqrt(N)$, being that $sqrt(N)^2 = N$, so $a <= sqrt(N)$.
• From the numbers we got in the previous point we can consider only half of them; even numbers if $N mod 2 = 0$, odd if $N mod 2 = 1$
• The bigger $a$ is, the smaller $b$.

So, summing it up, you can follow the algorithm suggested by @templatetypedef while keeping in mind the lower/upper limits of $a$ and $b$, and avoiding odd/even numbers depending on $N$. If you need the greates $a$ possible you just start with the greatest $a$ such that $a <= sqrt(N)$. If you need the smallest you can start with $a = 2$.

• This is not a good approach. It is far, far slower: its running time is $\Theta(N^{1/2})$, which is exoonentially slower than the strategy listed in the question. See my answer: cs.stackexchange.com/a/48060/755 – D.W. Oct 9 '15 at 16:27
• You're right actually. The linear approach is not so efficient. Nevertheless, by using the considerations on the possible values of $a$ given in here with your consideration on the possible values of $b$ and the binary search on the possible values of $a$ it should be a bit faster, even though in terms of complexity it remains $O((lg N)^2)$. – Gentian Kasa Oct 9 '15 at 16:52