cp's OEIS Frontend

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

%I A377125 #6 Nov 01 2024 21:30:36
%S A377125 1,2,4,5,8,10,19,28,50,77,140,232,400,682,1234,2153,3714,6825,12125,
%T A377125 22308,43065,79407,151201,291945,564267,1088341,2135410,4119306,
%U A377125 7849329,14826987,27802222,51646813,95519435,176054349,327888258,616082702,1171710821,2247355919
%N A377125 Number of subsets of the first n perfect powers whose sum is a perfect power.
%e A377125 a(6) = 10 subsets: {1}, {4}, {8}, {9}, {16}, {25}, {1, 8}, {9, 16}, {1, 8, 16} and {8, 16, 25}.
%o A377125 (Python)
%o A377125 from itertools import count
%o A377125 from sympy import perfect_power
%o A377125 from functools import cache
%o A377125 def cond(s): return bool(s == 1 or perfect_power(s))
%o A377125 @cache
%o A377125 def u(n):
%o A377125     if n == 1: return 1
%o A377125     return next(k for k in count(u(n-1)+1) if perfect_power(k))
%o A377125 @cache
%o A377125 def b(n, s):
%o A377125     assert type(s) == int, (n, s)
%o A377125     if n == 0: return int(cond(s))
%o A377125     return b(n-1, s) + b(n-1, s+u(n))
%o A377125 a = lambda n: b(n, 0)
%o A377125 print([a(n) for n in range(1, 41)]) # _Michael S. Branicky_, Oct 18 2024
%Y A377125 Cf. A001597, A339554.
%K A377125 nonn
%O A377125 1,2
%A A377125 _Ilya Gutkovskiy_, Oct 17 2024
%E A377125 a(23) and beyond from _Michael S. Branicky_, Oct 18 2024