Check if a number is a perfect power of another number
<p>For example, 243 is a perfect power of 3 because 243=3^5.</p>

<p>I've previously been using <code>(math.log(a) / math.log(b)).is_integer()</code>, which I thought worked fine, but then I tried it with the example above and it actually returns 4.999999999999999 due to floating point arithmetic. So it's only reliable for very small numbers, less than around 100 I've found.</p>

<p>I suppose I could use a loop to do repeated multiplication... i.e. set i to 3, then 9, then 27, then 81, then 243, which equals the target, so we know it's a perfect power. If it reaches a point where it's bigger than 243 then we know it's not a perfect power. But I'm running this check within a loop as it is, so this seems like it'd be very inefficient.</p>

<p>So is there any other way of reliably checking if a number is a perfect power of another?</p>

<p>If you want a speed up over repeated division for large numbers, you can make a list of all the exponents of the base where the exponent is a power of 2, and test those only.</p>

<p>For example, take 3<sup>9</sup>. 9 is 101 in binary, which is 2<sup>3</sup> + 2<sup>1</sup> = 8 + 1.</p>

<p>So 3<sup>9</sup> = 3<sup>8+1</sup> = 3<sup>2<sup>3</sup>+2<sup>1</sup></sup> = 3<sup>2<sup>3</sup></sup> x 3<sup>2<sup>1</sup></sup></p>

<p>You only need to trial divide twice, instead of 9 times.</p>

<pre><code>def is_power(a, b):
  if b == 0 or b == 1:
    return a == b
  if a &lt; b:
    return False
  c = []
  # make a list of the power of 2 exponents less than or equal to a:
  while b * b &lt;= a:
    c.append(b) 
    b = b * b
  # test against each of them where b &lt;= remaining a:
  while True: 
    if a % b != 0:
       return False
    a //= b
    while b &gt; a:
      if len(c) == 0:
        return a == 1
      b = c.pop()
  return True
</code></pre>

<p>Works for positive integers, e.g:</p>

<pre><code>print is_power(3**554756,3)
print is_power((3**554756)-1,3)
</code></pre>

<p>Output:</p>

<pre><code>True
False
</code></pre>

python math