OFFSET
1,2
COMMENTS
In the count 2^c of the cardinality of subsets of a set with cardinality c, the empty set - with sum 0 - is included; 2^c is just the row sum of the c-th row in the Pascal triangle.
Conjecture (confirmed through k=7): a(n)=k for all n in the interval A005318(k) <= n < A005318(k+1). - Jon E. Schoenfield, Nov 28 2013 [Note: This conjecture is false; see A276661 for a counterexample (n=34808712605260918463) in which n is in the interval A005318(66) <= n < A005318(67), yet a(n)=67, not 66. - Jon E. Schoenfield, Nov 05 2016]
A276661 is the main entry for the distinct subset sums problem. - N. J. A. Sloane, Apr 24 2024
LINKS
Fausto A. C. Cariboni, Table of n, a(n) for n = 1..220 (terms 1..120 from Jon E. Schoenfield)
T. Khovanova, The weight puzzle sequence, SeqFan Mailing list Aug 24 2010
T. Khovanova et al., The weights puzzle
Jon E. Schoenfield, Excel/VBA macro
EXAMPLE
Numbers n and an example of a subset of {1..n} exhibiting the maximum cardinality c=a(n):
1, {1}
2, {1, 2}
3, {1, 2}
4, {1, 2, 4}
5, {1, 2, 4}
6, {1, 2, 4}
7, {3, 5, 6, 7}
8, {1, 2, 4, 8}
9, {1, 2, 4, 8}
10, {1, 2, 4, 8}
11, {1, 2, 4, 8}
12, {1, 2, 4, 8}
13, {3, 6, 11, 12, 13}
14, {1, 6, 10, 12, 14}
15, {1, 6, 10, 12, 14}
16, {1, 2, 4, 8, 16}
17, {1, 2, 4, 8, 16}
18, {1, 2, 4, 8, 16}
For examples of maximum-cardinality subsets at values of n where a(n) > a(n-1), see A096858. - Jon E. Schoenfield, Nov 28 2013
MAPLE
# is any subset of L uniquely determined by its total weight?
iswts := proc(L)
local wtset, s, c, subL, thiswt ;
# the weight sums are to be unique, so sufficient to remember the set
wtset := {} ;
# loop over all subsets of weights generated by L
for s from 1 to nops(L) do
c := combinat[choose](L, s) ;
for subL in c do
# compute the weight sum in this subset
thiswt := add(i, i=subL) ;
# if this weight sum already appeared: not a candidate
if thiswt in wtset then
return false;
else
wtset := wtset union {thiswt} ;
end if;
end do:
end do:
# All different subset weights were different: success
return true;
end proc:
# main sequence: given grams 1 to n, determine a subset L
# such that each subset of this subset has a different sum.
wts := proc(n)
local s, c, L ;
# select sizes from n (largest size first) down to 1,
# so the largest is detected first as required by the puzzle.
for s from n to 1 by -1 do
# all combinations of subsets of s different grams
c := combinat[choose]([seq(i, i=1..n)], s) ;
for L in c do
# check if any of these meets the requir, print if yes
# and return
if iswts(L) then
print(n, L) ;
return nops(L) ;
end if;
end do:
end do:
print(n, "-") ;
end proc:
# loop for weights with maximum n
for n from 1 do
wts(n) ;
end do: # R. J. Mathar, Aug 24 2010
CROSSREFS
KEYWORD
nonn,nice
AUTHOR
N. J. A. Sloane, Nov 26 2011
EXTENSIONS
More terms from Alois P. Heinz, Nov 27 2011
More terms from Jon E. Schoenfield, Nov 28 2013
STATUS
approved