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

### 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)
```