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.

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