# What's the quickest way to check if an interger is a perfect power?

1. Oct 13, 2008

### redjoker

What's the quickest way to check if an integer is a perfect power?

I want to write a program that checks whether a consumed positive integer, n, is a perfect power or not. What would be the most efficient implementation of that program? I can think of an obvious implementation (checking if all 0 < i <= n/2 are power roots of n), but I'm rusty on number theory so I'm not sure if there exists a better way. I wouldn't want to get into case analysis, but if the gains in efficiency are significant, I'd consider it.

Last edited: Oct 13, 2008
2. Oct 13, 2008

### JasonRox

That's probably trickier than it sounds.

Is the number 36 considered a number of perfect power? Because that is 6^2 = 36.

That would make things very complicated.

3. Oct 13, 2008

### redjoker

Yes that's what I mean. If by complicated you mean slow, yeah you are right.

4. Oct 13, 2008

### Ben Niehoff

This way should be fast:

Call the number N_0:

1. Find how many times 2 goes into N_0; say N_0 = 2^A * N_1, where N_1 is an integer which is not divisible by 2.

2. Find how many times 3 goes into N_1. Let N_2 = N_1 / 3^B. If B > 0 and A != B, then fail. If B = 0 or B = A, then continue.

3. Repeat with the i-th prime on N_i in the same fashion until either N_i is prime or 1.

This algorithm takes advantage of the fact that if N is a perfect power, then the prime factorization of N must be of the form

(abcd...)^k = a^k * b^k * c^k * d^k * ...

Note that at every step in the iteration, you need only continue testing divisibility up to sqrt(N_i), NOT N_i/2. Since each N_i is less then the previous one, the algorithm has a worst-case complexity of

O(sqrt(N))

when N is prime, and on average, does better than that.

5. Oct 14, 2008

### CRGreathouse

A practical implementation to check if n is a perfect power (with exponent > 1):

1. For each small prime p, check how many times p goes into n. If the gcd of the exponents is 1, the number isn't a power with exponent > 1. (If 2^7 and 3^5 divide the number, gcd(7, 5) = 1 so it it's only a first power. If 2^12 and 7^4 divide the number, it may be a first, second, or fourth power.)

2. If you find a prime p where p^a divides n (but p^(a+1) does not) for a > 0, test if n is a kth power for each prime k dividing a. (If 2^14 but not 2^15 divides n, then test if n is a square or a 7th power.)

3. If you don't find a prime dividing the number, either try harder to find a factor (with ECM, perhaps) or trial divide up to the cube root of the number. If n has no factors below its cube root, it is a perfect power (exponent > 1) iff it is a square.

To check if a number is a k-th power, take the kth root of the number and see if it is an integer. A typical method of dealing with roundoff: take m = nearest_integer(pow(n + 0.5, 1.0/k)) and see if m^k is above n, below n, or equal to n. If equal, you're done (n is a kth power); if above or below, add or subtract one and see if the other number is on the opposite side. If m^k < n < (m+1)^k you know that n is not a kth power.

This method is faster than Ben's, with complexity O(n^(1/3)).

6. Oct 14, 2008

### Hurkyl

Staff Emeritus
It seems more straightforward to just compute the square root of N, the cube root N, et cetera. There are only log(N)/log(2) possibilities. Combining the techniques would probably be even faster, but probably not asymptotically faster.

7. Oct 14, 2008

### Ben Niehoff

It's also far more correct, as my algorithm neglected the case where the prime factors of N might have different powers, but still have a GCD greater than 1.

8. Oct 14, 2008

### Ben Niehoff

The catch is that computing the Nth root of a number is expensive. By carefully designing the algorithm, one can do everything with integers and not have to compute roots at all; thus avoiding both the expense and roundoff errors of floating point operations.

9. Oct 14, 2008

### Hurkyl

Staff Emeritus
Nevertheless, log(N) is much smaller than N^(1/3), unless N is so small that this whole discussion is moot. And besides, root extraction isn't as bad as you make it sound, especially if you're looking for integer roots. Newton's method converges quite quickly, and can be used modulo a sufficiently large power of 2 (i.e. in the 2-adic numbers) rather than working in the reals.

For what it's worth, GMP computes n-th roots.

10. Oct 14, 2008

### CRGreathouse

Oh yes, this is asymptotically much faster -- O(log^3 n) rather than O(n^(1/3)), assuming you use Newton's method for roots. You can even improve it to O(M(log n) log n/log log n) by taking only prime roots, which is about O(log^2 n) using S-S multiplication.

But if the numbers are large, I'd expect more care would be given to this problem then copying out pseudocode from a forum. You'd want to check the results modulo several small primes using reciprocity results; you'd want to use Bernstein's almost-linear prime power detection routine; you'd want a good pseudoprimality routine; you'd want careful meet-in-the-middle coding to determine how far primes are checked vs. how far roots are taken.

Or you'd want GMP.

11. Oct 14, 2008

### mathman

Re: What's the quickest way to check if an integer is a perfect power?

If you expect to do this for many integers, it might pay to generate a sorted list of perfect powers up to the largest number you could consider.

Then use a simple search algorithm to see if a given number is on the list.