I have the following code:

def isPP(n): pos = [int(i) for i in range(n+1)] pos = pos[2:] ##to ignore the trivial n** 1 == n case y = [] for i in pos: for it in pos: if i** it == n: y.append((i,it)) #return list((i,it)) #break if len(y) <1: return None else: return list(y[0])

Which works perfectly up until ~2000, since I’m storing far too much in memory. What can I do to make it work efficiently for large numbers (say, 50000 or 100000). I tried to make it end after finding one case, but my algorithm is still far too inefficient if the number is large.

Any tips?

## Answer

A number *n* is a perfect power if there exists a *b* and *e* for which *b*^*e* = *n*. For instance 216 = 6^3 = 2^3 * 3^3 is a perfect power, but 72 = 2^3 * 3^2 is not.

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 2^*e* will be greater than *n*. Further, it is only necessary to test prime *e*s, 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^15 = 32768 = 32^3 = 8^5 is a perfect cube root and also a perfect fifth root.

The function `isPerfectPower`

shown below tests each prime less than log2 *n* by first computing the integer root using Newton’s method, then powering the result to check if it is equal to *n*. Auxiliary function `primes`

compute a list of prime numbers by the Sieve of Eratosthenes, `iroot`

computes the integer *k*th-root by Newton’s method, and `ilog`

computes the integer logarithm to base *b* by binary search.

def primes(n): # sieve of eratosthenes i, p, ps, m = 0, 3, [2], n // 2 sieve = [True] * m while p <= n: if sieve[i]: ps.append(p) for j in range((p*p-3)/2, m, p): sieve[j] = False i, p = i+1, p+2 return ps def iroot(k, n): # assume n > 0 u, s, k1 = n, n+1, k-1 while u < s: s = u u = (k1 * u + n // u ** k1) // k return s def ilog(b, n): # max e where b**e <= n lo, blo, hi, bhi = 0, 1, 1, b while bhi < n: lo, blo, hi, bhi = hi, bhi, hi+hi, bhi*bhi while 1 < (hi - lo): mid = (lo + hi) // 2 bmid = blo * pow(b, (mid - lo)) if n < bmid: hi, bhi = mid, bmid elif bmid < n: lo, blo = mid, bmid else: return mid if bhi == n: return hi return lo def isPerfectPower(n): # x if n == x ** y, or False for p in primes(ilog(2,n)): x = iroot(p, n) if pow(x, p) == n: return x return False

There is further discussion of the perfect power predicate at my blog.