A377125 Number of subsets of the first n perfect powers whose sum is a perfect power.

1, 2, 4, 5, 8, 10, 19, 28, 50, 77, 140, 232, 400, 682, 1234, 2153, 3714, 6825, 12125, 22308, 43065, 79407, 151201, 291945, 564267, 1088341, 2135410, 4119306, 7849329, 14826987, 27802222, 51646813, 95519435, 176054349, 327888258, 616082702, 1171710821, 2247355919

Offset: 1

Author

Ilya Gutkovskiy, Oct 17 2024

Keywords

• nonn

Examples

			a(6) = 10 subsets: {1}, {4}, {8}, {9}, {16}, {25}, {1, 8}, {9, 16}, {1, 8, 16} and {8, 16, 25}.
		

Crossrefs

Cf. A001597, A339554.

Programs

Python

from itertools import count
from sympy import perfect_power
from functools import cache
def cond(s): return bool(s == 1 or perfect_power(s))
@cache
def u(n):
    if n == 1: return 1
    return next(k for k in count(u(n-1)+1) if perfect_power(k))
@cache
def b(n, s):
    assert type(s) == int, (n, s)
    if n == 0: return int(cond(s))
    return b(n-1, s) + b(n-1, s+u(n))
a = lambda n: b(n, 0)
print([a(n) for n in range(1, 41)]) # Michael S. Branicky, Oct 18 2024

Extensions

a(23) and beyond from Michael S. Branicky, Oct 18 2024