Perfect Power Predicate
March 13, 2012
A number n is a perfect power if there exists a b and e for which be = n. For instance 216 = 63 = 23 · 33 is a perfect power, but 72 = 23 · 32 is not. Testing for perfect powers is similar to other powering predicates we have seen, and is useful in some factoring algorithms.
The trick to determining if a number is a perfect power is to know that, if the number is a perfect power, then the exponent e must be less than log2 n, because if e is greater then 2e will be greater than n. Further, it is only necessary to test prime es, because if a number is a perfect power to a composite exponent it will also be a perfect power to the prime factors of the composite component; for instance, 215 = 32768 = 323 = 85 is a perfect cube root and also a perfect fifth root.
Your task is to write a function to determine if a number is a perfect power. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Pages: 1 2