# Optimizing runtime on finding the nth perfect power number

i was given a task to write a code to find the nth perfect power number. i wrote the following function to find that number but the runtime is long at high number (above 30). you can assume that the input number is within the range of 1-100. here's the code:

def perfect(n: int) -> int:
"""
:param n: enter the n'th place perfect power num you'd like
:return: the n'th perfect power number
"""
powers = []
i = 1
for i in range(0, n**2+1):
for k in range(0, i):
for m in range(0, i):
if m ** k == i:
powers.append(i)
i += 1
break
if len(powers) == n:
break
return powers[n-1]


### Naming

perfect is quite general for a function name. A better choice might be something like nth_perfect_power.

You have documented the function with a docstring comment, which is good. There is some repetition and verbosity however. I would perhaps use a single-line description, plus a description of what a perfect power is. You could also add some doctest examples:

def nth_perfect_power(n: int) -> int:
"""Return the n'th perfect power.

A perfect power is a positive integer of the form m ** k with
m >= 1 and k >= 2. Examples from https://oeis.org/A001597:

>>> nth_perfect_power(1)
1
>>> nth_perfect_power(10)
49
>>> nth_perfect_power(50)
1521
"""


Of course this is largely opinion-based.

### Review and performance improvements

The initial assignment

i = 1
for i in range(0, n**2+1):
// ...
i += 1


has no effect, and incrementing i within the loop makes the logic difficult to understand. Perhaps this is done to take care of duplicate powers such as $$\ 8^2 = 4^3 \$$, but there are better approaches to solve that. You can for example move the check for a perfect power to a separate function (where you can early-return).

Apart from the first perfect power $$\ i = 1 \$$ one only needs to check values $$\ m, k \ge 2 \$$.

The length of the powers array needs only to be checked again if we added an element, not for each value of $$\ i \$$.

The last element of an array can be retrieved as powers[-1].

Summarizing these topics so far, we get the following implementation:

def is_perfect_power(i: int) -> bool:
if i == 1:
return True
for k in range(2, i):
for m in range(2, i):
if m ** k == i:
return True
return False

def nth_perfect_power(n: int) -> int:
powers = []
for i in range(1, n**2 + 1):
if is_perfect_power(i):
powers.append(i)
if len(powers) == n:
break
return powers[-1]


This is more code than your original, but easier to read and slightly more efficient. It can be improved further: The exponentiation $$\ m^k \$$ can be replaced by repeated multiplication with $$\ m \$$. Also the inner loop can be exited as soon as a power is larger than the candidate $$\ i \$$:

def is_perfect_power(i: int) -> bool:
if i == 1:
return True
for m in range(2, i):
p = m * m
while p < i:
p *= m
if p == i:
return True
return False


With these changes, the $$\ 20^\text{th} \$$ perfect power is found in approx. 3 milliseconds (compared to 2.6 seconds with your original code), and the $$\ 100^\text{th} \$$ perfect power is found in approx. 2.5 seconds.

### A different approach

Your code determines for every candidate $$\ i \$$ if it is a perfect power by computing $$\ m^k \$$ for all $$\ m, k \$$ in the range $$\ 0, \ldots, i \$$. This is done for all $$\i \$$ up to $$\ n^2\$$, until $$\ n \$$ perfect powers are found.

As an example, in order to find the $$\ 20^\text{th} \$$ perfect power, $$\ m^k \$$ is computed $$\ 3382670\$$ times.

We already improved that by restricting the base $$\ m \$$ and the exponent $$\ k \$$ to smaller ranges. But for larger values of $$\ n \$$ we need a different approach.

It is much more efficient to compute all perfect powers (in some range) instead, and then take the $$\ n^\text{th} \$$ smallest number. Since there can be duplicates (e.g. $$\ 8^2 = 4^3 \$$), a set should be used to collect the perfect powers.

You already used that there must be $$\ n \$$ perfect numbers in the range $$\ 1, \ldots, n^2 \$$. This can still be used to limit the range of the exponent $$\ k \$$.

As an example, in order to find the $$\ 20^\text{th} \$$ perfect power we need the numbers $$\ m^k \$$ in the range $$\1, \ldots, 400 \$$. The first perfect number $$\ 1 \$$ can be handled separately, so that $$\ m \ge 2 \$$ and $$\ k \ge 2 \$$:

\begin{align} m&=2: 4, 8, 16, 32, 64, 128, 256 \\ m&=3: 9, 27, 81, 243 \\ m&=4: 16, 64, 256 \\ m&=5: 25, 125 \\ m&=6: 35, 216 \\ m&=7: 49, 343 \\ m&=8: 64 \\ \vdots \\ m&=20: 400 \end{align}

This leads to the following implementation:

def nth_perfect_power(n: int) -> int:
upper_limit = n * n
powers = set()
for m in range(2, n + 1):
p = m * m
while p <= upper_limit:
p *= m
return sorted(powers)[n-1]


This finds the $$\ 100000^\text{th} \$$ perfect power is found in approx. 0.1 seconds, and the one-millionth perfect power in approx. 1.4 seconds.

For even more performance, we can use a heap structure to store only the $$\ n \$$ smallest powers found so far. The Python heapq is a min-heap but we need a max-heap. Therefore all powers are multiplied by $$\(-1)\$$. We start with the list of squares and then add the third, fourth, ... powers. For every base $$\ m \$$ we can stop as soon as $$\ p = m^k \$$ is larger than the $$\ n \$$ smallest powers found so far.

Implementation:

def nth_perfect_power(n: int) -> int:
heap = [- i * i for i in range(1, n+1)]
heapq.heapify(heap)
powers = set(heap)
for m in range(2, n + 1):
p = - m * m * m
if p <= heap:
break
while p > heap:
if not p in powers:
powers.remove(heapq.heappushpop(heap, p))

• Your powers set could be written as a "one-liner", (not that doing so will make it any more readable). powers = {1} | {m ** k for m in range(2, n+1) for k in range(2, floor(log(n*n,m)+1))} . Of course you need from math import floor, log. Using $\log_{m}{n^2}$ as the upper limit of the range of k avoids the need to constantly test if p has exceeded n², and precomputing n² instead of calculating it every time would shave off a few microseconds too. – AJNeufeld Apr 16 at 20:25
• I'm getting a 21.8% speedup with the set-comprehension & $log_{m}{n²}$ method over your original method, on the 100,000th perfect power. Still under a second for up to n = 600,000. – AJNeufeld Apr 16 at 20:46
• For the max-heap, you can use heapq._heapify_max(). And unless I'm thinking wrong, you could shave off a full iteration of the "heap-list" by building the heapq and the set in the same loop. – ades Apr 17 at 10:19