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>I think a better way would be implementing this "hack":</p>

<pre><code>import math

def isPP(n):
    range = math.log(n)/math.log(2)
    range = (int)(range)
    result = []
    for i in xrange(n):
        if(i&lt;=1):
            continue
        exponent = (int)(math.log(n)/math.log(i))
        for j in [exponent-1, exponent, exponent+1]:
            if i ** j == n:
                result.append([i,j])
    return result

print isPP(10000)
</code></pre>

<p>Result:</p>

<pre><code>[[10,4],[100,2]]
</code></pre>

<p>The hack uses the fact that:</p>

<pre><code>if log(a)/log(b) = c,
    then power(b,c) = a
</code></pre>

<p>Since this calculation can be a bit off in floating points giving really approximate results, exponent is checked to the accuracy of <code>+/- 1</code>.</p>

<p>You can make necessary adjustments for handling corner cases like <code>n=1, etc.</code></p>

python algorithm python-3.x