A126024 Number of subsets of {1,2,3,...,n} whose sum is a square integer (including the empty subset).

1, 2, 2, 3, 5, 7, 12, 20, 34, 60, 106, 190, 346, 639, 1183, 2204, 4129, 7758, 14642, 27728, 52648, 100236, 191294, 365827, 700975, 1345561, 2587057, 4981567, 9605777, 18546389, 35851756, 69382558, 134414736, 260658770, 505941852, 982896850

Offset

0,2

Links

Alois P. Heinz, Table of n, a(n) for n = 0..990 (terms n=1..100 from T. D. Noe)

Example

The subsets of {1,2,3,4,5} that sum to a square are {}, {1}, {1,3}, {4}, {2,3,4}, {1,3,5} and {4,5}. Thus a(5)=7.

Maple

b:= proc(n, i) option remember; (m->
      `if`(n=0 or n=m, 1, `if`(n<0 or n>m, 0, b(n, i-1)+
      `if`(i>n, 0, b(n-i, i-1)))))(i*(i+1)/2)
    end:
a:= proc(n) option remember; `if`(n<0, 0, a(n-1)+
      add(b(j^2-n, n-1), j=isqrt(n)..isqrt(n*(n+1)/2)))
    end:
seq(a(n), n=0..50);  # Alois P. Heinz, Feb 02 2017

Mathematica

g[n_] := Block[{p = Product[1 + z^i, {i, n}]}, Sum[Boole[IntegerQ[Sqrt[k]]]*Coefficient[p, z, k], {k, 0, n*(n + 1)/2}]]; Array[g, 35] (* Ray Chandler, Mar 05 2007 *)

Prog

(Haskell)
import Data.List (subsequences)
a126024 = length . filter ((== 1) . a010052 . sum) .
                          subsequences . enumFromTo 1
-- Reinhard Zumkeller, Feb 22 2012, Oct 27 2010

Crossrefs

Cf. A053632, A127542.

Cf. A181522. - Reinhard Zumkeller, Oct 27 2010

Cf. A010052, A284250.

Row sums of A281871.

Sequence in context: A060699 A284909 A062724 * A179316 A103597 A337745

Adjacent sequences: A126021 A126022 A126023 * A126025 A126026 A126027

Keyword

nonn

Author

John W. Layman, Feb 27 2007

Extensions

Extended by Ray Chandler, Mar 05 2007

a(0)=1 prepended by Alois P. Heinz, Jan 30 2017

Status

approved