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

Links

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

Eric Weisstein's World of Mathematics, Perfect Power

Example

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

Prog

(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

Crossrefs

Cf. A001597, A126024, A126111, A339555.

Sequence in context: A007176 A267757 A176691 * A274355 A351100 A054253

Adjacent sequences: A339551 A339552 A339553 * A339555 A339556 A339557

Keyword

nonn

Author

Ilya Gutkovskiy, Dec 08 2020

Extensions

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

Status

approved