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

  • Thread starter redjoker
  • Start date
  • Tags
    Power
In summary, there are multiple ways to efficiently check if a positive integer is a perfect power. One method involves finding the prime factorization of the number and checking if the exponents have a common factor. Another method involves trial division and taking the Nth root of the number. However, this can be expensive and prone to roundoff errors. A more precise and faster method involves using integer operations and modular arithmetic. These techniques can improve the asymptotic complexity from O(n^(1/3)) to O(log^3 n). Additionally, using prime roots and implementing other optimizations can further improve the efficiency of the algorithm.
  • #1
redjoker
5
0
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:
Mathematics news on Phys.org
  • #2
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
Yes that's what I mean. If by complicated you mean slow, yeah you are right.
 
  • #4
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
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
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
CRGreathouse said:
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.
 
  • #8
Hurkyl said:
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.
 
  • #9
Ben Niehoff said:
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.
 
  • #10
Hurkyl said:
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.

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

Or you'd want GMP. :redface:
 
  • #11


redjoker said:
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.
 

1. How do you define a perfect power?

A perfect power is a positive integer that can be expressed as a power of another positive integer. In other words, it is a number that can be written in the form of an, where a and n are both positive integers.

2. What is the quickest way to check if an integer is a perfect power?

The quickest way to check if an integer is a perfect power is by using the integer square root function. This function calculates the largest integer whose square is less than or equal to the given integer. If the result of the integer square root function is equal to the given integer, then it is a perfect power.

3. Can all positive integers be expressed as perfect powers?

No, not all positive integers can be expressed as perfect powers. For example, the numbers 2, 3, 5, 6, and 7 cannot be expressed as perfect powers.

4. Are there any efficient algorithms for checking if an integer is a perfect power?

Yes, there are efficient algorithms for checking if an integer is a perfect power. One such algorithm is the Pollard's rho algorithm. This algorithm uses a random sequence to find factors of a number, and if the factors are perfect powers, then the number is a perfect power itself.

5. How can knowing if an integer is a perfect power be useful in mathematics?

Knowing if an integer is a perfect power can be useful in various areas of mathematics, such as number theory, cryptography, and coding theory. It can also help in solving problems related to Diophantine equations, which involve finding integer solutions to polynomial equations.

Similar threads

Replies
11
Views
2K
  • General Math
Replies
1
Views
1K
  • General Math
Replies
13
Views
1K
Replies
14
Views
1K
Replies
9
Views
1K
  • Electrical Engineering
Replies
2
Views
392
  • Aerospace Engineering
Replies
10
Views
1K
  • General Math
Replies
3
Views
967
Replies
2
Views
785
Back
Top