Programming Praxis

A number n is a perfect power if there exists a b and e for which b^e = n. For instance 216 = 6³ = 2³ · 3³ is a perfect power, but 72 = 2³ · 3² 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 log₂ n, because if e is greater then 2^e 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, 2¹⁵ = 32768 = 32³ = 8⁵ 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