cp's OEIS Frontend

A339554 Number of subsets of {1..n} whose sum is a perfect power.

%I A339554 #21 Feb 16 2025 08:34:01
%S A339554 1,1,2,5,9,15,25,48,99,187,326,543,896,1497,2568,4554,8504,17074,
%T A339554 36011,75842,153964,298835,561337,1044317,1968266,3796589,7448571,
%U A339554 14648620,28541211,54900185,104612044,198620706,377264405,717303565,1363083731,2585928327
%N A339554 Number of subsets of {1..n} whose sum is a perfect power.
%H A339554 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PerfectPower.html">Perfect Power</a>
%e A339554 a(6) = 15 subsets: {1}, {4}, {1, 3}, {2, 6}, {3, 5}, {3, 6}, {4, 5}, {1, 2, 5}, {1, 2, 6}, {1, 3, 4}, {1, 3, 5}, {2, 3, 4}, {1, 4, 5, 6}, {2, 3, 5, 6} and {1, 2, 3, 4, 6}.
%o A339554 (Python)
%o A339554 from sympy import perfect_power
%o A339554 from functools import lru_cache
%o A339554 @lru_cache(maxsize=None)
%o A339554 def b(n, s, c):
%o A339554   if n == 0:
%o A339554     if c > 0 and (s==1 or perfect_power(s)): return 1
%o A339554     return 0
%o A339554   return b(n-1, s, c) + b(n-1, s+n, c+1)
%o A339554 a = lambda n: b(n, 0, 0)
%o A339554 print([a(n) for n in range(1, 37)]) # _Michael S. Branicky_, Dec 10 2020
%Y A339554 Cf. A001597, A126024, A126111, A339555.
%K A339554 nonn
%O A339554 1,3
%A A339554 _Ilya Gutkovskiy_, Dec 08 2020
%E A339554 a(25)-a(36) from _Alois P. Heinz_, Dec 08 2020