6
\$\begingroup\$

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] 
\$\endgroup\$
6
\$\begingroup\$

Naming

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

Docstring comments

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([1])
    for m in range(2, n + 1):
        p = m * m
        while p <= upper_limit:
            powers.add(p)
            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[0]:
            break
        while p > heap[0]:
            if not p in powers:
                powers.remove(heapq.heappushpop(heap, p))
                powers.add(p)
            p *= m
    return -heap[0]

This computes the one-millionth perfect power in approx. 0.42 seconds.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – AJNeufeld Apr 16 at 20:25
  • \$\begingroup\$ @AJNeufeld: You are totally right. I had thought of that but decided to keep it simple (and for n <= 100 it probably does not make a big difference). \$\endgroup\$ – Martin R Apr 16 at 20:31
  • 1
    \$\begingroup\$ @AJNeufeld: Precomputing n^2 also makes the code more self-documenting, so I have taken up your suggestion. Thank you for the feedback. \$\endgroup\$ – Martin R Apr 16 at 20:38
  • \$\begingroup\$ 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. \$\endgroup\$ – AJNeufeld Apr 16 at 20:46
  • \$\begingroup\$ 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. \$\endgroup\$ – ades Apr 17 at 10:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.