|
|
A126024
|
|
Number of subsets of {1,2,3,...,n} whose sum is a square integer (including the empty subset).
|
|
12
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
LINKS
|
|
|
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:
|
|
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
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|