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.

Advertisements

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(a)
        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:
        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 Reply

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

WordPress.com Logo

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

Google+ photo

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

Twitter picture

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

Facebook photo

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

Connecting to %s

%d bloggers like this: