Register to reply 
What's the quickest way to check if an interger is a perfect power? 
Share this thread: 
#1
Oct1308, 09:07 PM

P: 5

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.



#2
Oct1308, 09:50 PM

HW Helper
PF Gold
P: 2,327

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
Oct1308, 10:04 PM

P: 5

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



#4
Oct1308, 10:30 PM

Sci Advisor
P: 1,594

What's the quickest way to check if an interger is a perfect power?
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 ith 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 worstcase complexity of O(sqrt(N)) when N is prime, and on average, does better than that. 


#5
Oct1408, 12:25 AM

Sci Advisor
HW Helper
P: 3,684

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 kth 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
Oct1408, 12:48 AM

Emeritus
Sci Advisor
PF Gold
P: 16,091

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
Oct1408, 03:54 AM

Sci Advisor
P: 1,594




#8
Oct1408, 04:02 AM

Sci Advisor
P: 1,594




#9
Oct1408, 04:41 AM

Emeritus
Sci Advisor
PF Gold
P: 16,091

For what it's worth, GMP computes nth roots. 


#10
Oct1408, 08:51 AM

Sci Advisor
HW Helper
P: 3,684

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 almostlinear prime power detection routine; you'd want a good pseudoprimality routine; you'd want careful meetinthemiddle coding to determine how far primes are checked vs. how far roots are taken. 


#11
Oct1408, 03:47 PM

Sci Advisor
P: 6,080

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


Register to reply 
Related Discussions  
Quickest Way to Learn QM  Academic Guidance  10  
Power check and help  Introductory Physics Homework  3  
Power Question: Just Check My Work!  Introductory Physics Homework  15  
Negative numbers to noninterger powers  General Math  11  
Quickest Question Ever.  Introductory Physics Homework  15 