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

[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.

 

[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.

 

[redjoker]

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

 

[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.

 

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

 

[Hurkyl]

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.

 

[Ben Niehoff]

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

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.

 

[Ben Niehoff]

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.

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.

 

[Hurkyl]

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.

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.

 

[CRGreathouse]

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.

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.

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

Or you'd want GMP.

 

[mathman]

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.

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.