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

Author

John W. Layman, Feb 27 2007

Keywords

• nonn

Examples

			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.
		

Links

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

Crossrefs

Cf. A053632, A127542.

Cf. A181522. - Reinhard Zumkeller, Oct 27 2010

Cf. A010052, A284250.

Row sums of A281871.

Programs

Haskell

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

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 *)

Extensions

Extended by Ray Chandler, Mar 05 2007

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