A377125 - OEIS

%I #6 Nov 01 2024 21:30:36

%S 1,2,4,5,8,10,19,28,50,77,140,232,400,682,1234,2153,3714,6825,12125,

%T 22308,43065,79407,151201,291945,564267,1088341,2135410,4119306,

%U 7849329,14826987,27802222,51646813,95519435,176054349,327888258,616082702,1171710821,2247355919

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

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

%o (Python)

%o from itertools import count

%o from sympy import perfect_power

%o from functools import cache

%o def cond(s): return bool(s == 1 or perfect_power(s))

%o @cache

%o def u(n):

%o     if n == 1: return 1

%o     return next(k for k in count(u(n-1)+1) if perfect_power(k))

%o @cache

%o def b(n, s):

%o     assert type(s) == int, (n, s)

%o     if n == 0: return int(cond(s))

%o     return b(n-1, s) + b(n-1, s+u(n))

%o a = lambda n: b(n, 0)

%o print([a(n) for n in range(1, 41)]) # _Michael S. Branicky_, Oct 18 2024

%Y Cf. A001597, A339554.

%K nonn

%O 1,2

%A _Ilya Gutkovskiy_, Oct 17 2024

%E a(23) and beyond from _Michael S. Branicky_, Oct 18 2024