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 both the base and exponent are wildcards here and you are starting with only the "big number" result, then you're going to face a speed-memory trade-off. Since you seem to have implied that nested loops would be "inefficient", I assume that CPU cycle efficiency is important to you. In this case, may I suggest pre-computing a bunch of base-exponent pairs: a kind of rainbow table if you will. This will consume more memory, but much less CPU cycles. Then you can simply iterate over your table and see if you find a match. Or, if you're <em>very</em> concerned about speed, you can even sort the table and do a a binary search. You can even store the pre-computed table in a file, if you like.</p>

<p>Also, you didn't specify whether you just want a yes/no answer, or whether you are trying to find the corresponding base and exponent of the power. So I'll assume you want to find <strong>a</strong> base-exponent pair (some perfect powers will have multiple base-exponent solutions).</p>

<p>Try this on for size (I'm using Python 3):</p>

<pre><code>#Setup the table as a list
min_base = 2 #Smallest possible base
max_base = 100 #Largest possible base
min_exp = 2 #Smallest possible exponent
max_exp = 10 #Largest possible exponent
powers = []

#Pre-compute the table - this takes time, but only needs to be done once
for i in range(min_base, max_base+1):
    for j in range(min_exp, max_exp+1):
        powers.append([i, j, i ** j])

#Now sort the table by the 3'rd element - again this is done only once
powers.sort(key=lambda x: x[2])


#Binary search the table to check if a number is a perfect power
def is_perfect_power(a, powers_arr):
    lower = 0
    upper = len(powers_arr)
    while lower &lt; upper:
        x = lower + (upper - lower) // 2
        val = powers_arr[x][2] #[2] for the pre-computed power
        if a == val:
            return powers_arr[x][0:2]
        elif a &gt; val:
            if lower == x:
                break
            lower = x
        elif a &lt; val:
            upper = x
    return False #Number supplied is not a perfect power

#A simple demonstration
print(is_perfect_power(243, powers)) #Output is [3, 5]
print(is_perfect_power(105413504, powers)) #Output is [14, 7]
print(is_perfect_power(468209, powers)) #Output is False - not a perfect power
</code></pre>

<p>Someone more mathematically inclined may have a more efficient answer, but this should get you started. On my machine this runs pretty fast.</p>

python math