Perfect Power

A Power Number is defined as a number greater than zero that can be expressed as X^Y, where X and Y are integers greater than one. Thus, the first few (in order) are:

4 (2^2) 
8 (2^3)
9 (3^2) 
16 (2^4, 4^2)
25 (5^2) 
27 (3^3) 
32 (2^5) 
36 (6^2)

This function takes an integer i and returns the (zero-indexed) ith power number. Some examples:

getPowerNumber(0) -> 4 
getPowerNumber(3) -> 16 
getPowerNumber (8) -> 49

Approach 1: Brute Force

The Idea: A perfect power begins at the power and exponent position 2^2. Then it could proceed in either one of two directions (to the left it, or to the element below it). That is, it can either transition to 2^3 or 3^2 from 2^2. As far we know for now, the result can exist is either direction, so both siblings are added to the queue. Repeat this step for the next element in the queue. Notice how doing so covers the entirety of the matrix.

Complexity: O(nlogn) time. The priority queue has to manage at least one more element than it takes out, so its size increases linearly, and so each subsequent operation will take log(k+1) more work, where k begins at 0 and increases by one n amount of times where n is the total number of elements in the matrix. O(n/2) space

import queue


def getPowerNumber(index):
    """
    :param index: [int] index for power number
    :return: [int] the nth zero-indexed power number
    """

    if index < 0:
        raise ValueError("Index must be zero or greater.")

    q = queue.PriorityQueue()
    q.put((4, 2, 2))  # index 0 start

    cur_index, last_pow = 0, 0
    while cur_index <= index:
        parent = q.get()
        next_pow, num, exp = parent[0], parent[1], parent[2]
        if next_pow != last_pow:
            cur_index += 1
        last_pow = next_pow
        q.put((num ** (exp + 1), num, exp + 1))
        q.put(((num + 1) ** exp, num + 1, exp))

    return last_pow


for i in range(100):
    print(i, getPowerNumber(i))

Approach 2: Heap Generators

The Idea: The technique that I'll go through here is really cool. If we combine generators with a heap, all of our micro operations can be managed within the heap and the logic of the code simplifies. First, begin with i generators, where i is [0...index] . Each generator carries out infinite operation of i^n for n=[0,1,2...inf]. Our heap will continue to maintain i generator objects, but our root of our heap will contain the current minimum value held to a generator. Calling next() on this generator object will place it elsewhere in the tree, and the next minimum generator object will appear upfront. Complexity: O(nlogn) time and O(n) space where n is the index

# credits go to Morphiaaa on github
import heapq


def pn_generator(num):
    p = 2
    while True:
        yield num ** p
        p += 1

def getPowerNumber(index):
    pn = [pn_generator(i) for i in range(2, index + 3)]
    pn_pool = heapq.merge(*pn)
    i, last_pn = 0, 0

    while i <= index:
        power = next(pn_pool)
        if power != last_pn:
            i += 1
        last_pn = power
    return power


print(getPowerNumber(2000))