Top Heavy Perfect Powers

July 17, 2018

This isn’t hard, as we have a test for perfect powers in a previous exercise:

> (let ((result '()))
  (define (lt? a b) (< (expt (car a) (cadr a)) (expt (car b) (cadr b))))
  (do ((b 2 (+ b 1))) ((< #e1e100 (expt b b)) (sort lt? result))
    (do ((n b (+ n 1))) ((< #e1e100 (expt b n)))
      (when (not (perfect-power? b))
        (set! result (cons (list b n) result))))))
((2 2) (2 3) (2 4) (3 3) (2 5) (2 6) (3 4) (2 7) (3 5) (2 8) (2 9) (3 6)
(2 10) (2 11) (3 7) (5 5) (2 12) (3 8) (2 13) (5 6) (2 14) (3 9) (2 15)
... 2372 values elided ...
(6 128) (2 331) (43 61) (56 57) (17 81) (14 87) (3 209) (7 118) (19 78)
(46 60) (28 69) (31 67) (2 332) (5 143) (15 85) (11 96) (41 62) (10 100))

You can run the program, and see the complete output, at https://ideone.com/lKIDpu.

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: