|
| |
|
|
A208531
|
|
Number of distinct sums of subsets of the first n squares {1,4,9,...,n^2}.
|
|
2
|
|
|
|
2, 4, 8, 16, 28, 52, 89, 147, 224, 324, 445, 589, 758, 954, 1179, 1435, 1724, 2048, 2409, 2809, 3250, 3734, 4263, 4839, 5464, 6140, 6869, 7653, 8494, 9394, 10355, 11379, 12468, 13624, 14849, 16145, 17514, 18958, 20479, 22079
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
From the 9th term onward the differences of this sequence appear to again be the squares. Is there a simple explanation for this?
Similar examples are provided for the positive integers in A000124, the odd integers in A082562 and the primes in A082548.
To compute the terms in order, start with a list with the element 0. Add 1^2 to each term of the list and add the sum to the list, if it isn't already on the list. The cardinality of the list is a(1). Then a(n+1) is computed by adding n^2 to each member of the list and adding the sum to the list, if it isn't already there. The number of members of the list is a(2). This is much faster than considering every subset. Jud McCranie, Mar 01 2012
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = (2*n^3+3*n^2+n-366)/6 for n>8.
a(n) = 4*a(n-1)-6*a(n-2)+4*a(n-3)-a(n-4) for n>12.
G.f.: x*(2-4*x+4*x^2-2*x^4+8*x^5-7*x^6+7*x^7-10*x^8+6*x^9-6*x^10+4*x^11) / (1-x)^4. (End)
For a proof of these conjectures see the Suzuki (2019) link.
|
|
|
EXAMPLE
|
All subsets of {1,4,9,16} give distinct sums, so a(4)=16. Four pairs of subsets of {1,4,9,16,25} have the same sum, for example {9,16} and {25}, resulting in a(5)=28.
|
|
|
MATHEMATICA
|
Table[Length[Union[Total /@ Subsets[Range[n]^2]]], {n, 17}] (* T. D. Noe, Feb 28 2012 *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
