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.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
2 Comments »

2 Responses to “Top Heavy Perfect Powers”

  1. Paul said
    July 18, 2018 at 6:16 AM

    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))  # ->2413
  2. Daniel said
    July 20, 2018 at 3:09 AM

    Here’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:

    (2, 2)
(2, 3)
(2, 4)
(3, 3)
(2, 5)
(2, 6)
(3, 4)
...
(2, 332)
(5, 143)
(15, 85)
(11, 96)
(41, 62)
(10, 100)

Leave a comment