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

1, 1, 2, 5, 9, 15, 25, 48, 99, 187, 326, 543, 896, 1497, 2568, 4554, 8504, 17074, 36011, 75842, 153964, 298835, 561337, 1044317, 1968266, 3796589, 7448571, 14648620, 28541211, 54900185, 104612044, 198620706, 377264405, 717303565, 1363083731, 2585928327

Offset: 1

Author

Ilya Gutkovskiy, Dec 08 2020

Keywords

• nonn

Examples

			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}.
		

Links

• Eric Weisstein's World of Mathematics, Perfect Power

Crossrefs

Cf. A001597, A126024, A126111, A339555.

Programs

Python

from sympy import perfect_power
from functools import lru_cache
@lru_cache(maxsize=None)
def b(n, s, c):
  if n == 0:
    if c > 0 and (s==1 or perfect_power(s)): return 1
    return 0
  return b(n-1, s, c) + b(n-1, s+n, c+1)
a = lambda n: b(n, 0, 0)
print([a(n) for n in range(1, 37)]) # Michael S. Branicky, Dec 10 2020

Extensions

a(25)-a(36) from Alois P. Heinz, Dec 08 2020