How to make perfect power algorithm more efficient?
<p>I have the following code:</p>

<pre><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) &lt;1:
      return None
  else:
      return list(y[0])
</code></pre>

<p>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.</p>

<p>Any tips?</p>

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

<p>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 <em>e</em> must be less than log2 <em>n</em>, because if <em>e</em> is greater then 2^<em>e</em> will be greater than <em>n</em>. Further, it is only necessary to test prime <em>e</em>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.</p>

<p>The function <code>isPerfectPower</code> shown below tests each prime less than log2 <em>n</em> by first computing the integer root using Newton's method, then powering the result to check if it is equal to <em>n</em>. Auxiliary function <code>primes</code> compute a list of prime numbers by the Sieve of Eratosthenes, <code>iroot</code> computes the integer <em>k</em>th-root by Newton's method, and <code>ilog</code> computes the integer logarithm to base <em>b</em> by binary search.</p>

<pre><code>def primes(n): # sieve of eratosthenes
    i, p, ps, m = 0, 3, [2], n // 2
    sieve = [True] * m
    while p &lt;= 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 &gt; 0
    u, s, k1 = n, n+1, k-1
    while u &lt; s:
        s = u
        u = (k1 * u + n // u ** k1) // k
    return s

def ilog(b, n): # max e where b**e &lt;= n
    lo, blo, hi, bhi = 0, 1, 1, b
    while bhi &lt; n:
        lo, blo, hi, bhi = hi, bhi, hi+hi, bhi*bhi
    while 1 &lt; (hi - lo):
        mid = (lo + hi) // 2
        bmid = blo * pow(b, (mid - lo))
        if n &lt; bmid: hi, bhi = mid, bmid
        elif bmid &lt; 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
</code></pre>

<p>There is further discussion of the perfect power predicate at <a href="https://programmingpraxis.com/2012/03/13/perfect-power-predicate/" rel="nofollow">my blog</a>.</p>

python algorithm python-3.x