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,2

Links

Table of n, a(n) for n=1..38.

Example

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

Prog

(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

Crossrefs

Cf. A001597, A339554.

Sequence in context: A018589 A190141 A018631 * A050554 A018722 A018767

Adjacent sequences: A377122 A377123 A377124 * A377126 A377127 A377128

Keyword

nonn

Author

Ilya Gutkovskiy, Oct 17 2024

Extensions

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

Status

approved