# 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

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

``````# 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))``````

Last updated