Top Heavy Perfect Powers
July 17, 2018
Over at his blog, Ken is investigating top-heavy perfect powers to investigate increasing the breadth of the Cunningham project. He makes a list of 2413 perfect powers bn with b ≤ n in increasing order, up to a googol, omitting bases that are themselves perfect powers (for instance, 4n, 8n or 9n).
Your task is to make a list of the 2413 top-heavy perfect powers less than a googol. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
In Python. The prime generator and the iroot function are omitted.
from itertools import count, takewhile, dropwhile from heapq import merge from ma.primegen import primegen from ma.mymath import iroot def is_perfect_power(n): """returns (b, e) if b**e == n else False""" if n < 4 or not isinstance(n, int): return False for prime in primegen(): r = iroot(prime, n) if r < 2: return False if r**prime == n: return r, prime def gen(b): """generator for all powers of b""" return (b**n for n in count(b)) def top_heavy(limit): bmax = next(dropwhile(lambda x: x**x <= limit, count(2))) bs = [i for i in range(2, bmax) if not is_perfect_power(i)] iters = [gen(b) for b in bs] yield from takewhile(lambda x: x <= limit, merge(*iters)) if __name__ == "__main__": a = list(top_heavy(10**100)) print(a) print(len(a)) # ->2413Here’s a solution in Python.
from itertools import count def top_heavy_pps(limit): lookup = dict() for x in count(2): if x in lookup: continue for y in count(x): pp = x ** y if pp > limit: break if pp in lookup: continue lookup[pp] = (x, y) if y == x: break return [lookup[pp] for pp in sorted(lookup)] if __name__ == "__main__": results = top_heavy_pps(10 ** 100) assert len(results) == 2413 for result in results: print(result)Output: