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.
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)) # ->2413Here’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: