login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A339554 Number of subsets of {1..n} whose sum is a perfect power. 1
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 25 23:53 EDT 2022. Contains 354869 sequences. (Running on oeis4.)