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 bn 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

2 Responses to “Top Heavy Perfect Powers”

  1. Paul said

    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(len(a))  # ->2413
  2. Daniel said

    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:


    (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 Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: