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 will be working with large numbers, you may want to look at <a href="https://pypi.python.org/pypi/gmpy2" rel="nofollow">gmpy2</a>. <code>gmpy2</code> provides access to the GMP multiple-precision library. One of the functions provided is <code>is_power()</code>. It will return True if the argument is a perfect power of some base number. It won't provide the power or the base number but it will quickly filter out numbers that can not be perfect powers.</p>

<pre><code>&gt;&gt;&gt; import gmpy2
&gt;&gt;&gt; [n for n in range(1,1000) if gmpy2.is_power(n)]
[1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100, 121, 125, 128, 144, 169, 196, 216, 225, 243, 256, 289, 324, 343, 361, 400, 441, 484, 512, 529, 576, 625, 676, 729, 784, 841, 900, 961]
</code></pre>

<p>Once you've identified possible powers, then you can use <code>iroot_rem(x,n)</code> to find the nth root and remainder of x. Then once you find a valid exponent, you can find the base number. Here is an example that searches through a range for all possible perfect powers.</p>

<pre><code>&gt;&gt;&gt; for x in range(1,1000):
...   if gmpy2.is_power(x):
...     for e in range(x.bit_length(), 1, -1):
...       temp_root, temp_rem = gmpy2.iroot_rem(x, e)
...       if not temp_rem:
...         print x, temp_root, e
... 
4 2 2
8 2 3
9 3 2
16 2 4
16 4 2
25 5 2
27 3 3
32 2 5
36 6 2
49 7 2
64 2 6
64 4 3
64 8 2
81 3 4
81 9 2
&lt;&lt; remainder clipped&gt;&gt;
</code></pre>

<p>Disclaimer: I maintain <code>gmpy2</code>.</p>

python math