|
%I #57 Jan 02 2023 12:30:48
%S 1,2,2,3,3,3,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,5,6,6,6,6,6,6,6,6,6,6,6,
%T 6,6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
%U 7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,8,8,8,8
%N a(n) is the maximal number c of integers that can be chosen from {1,2,...,n} so that all 2^c subsets have distinct sums.
%C 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.
%C 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]
%H Fausto A. C. Cariboni, <a href="/A201052/b201052.txt">Table of n, a(n) for n = 1..220</a> (terms 1..120 from Jon E. Schoenfield)
%H T. Khovanova, <a href="http://list.seqfan.eu/oldermail/seqfan/2010-August/005757.html">The weight puzzle sequence</a>, SeqFan Mailing list Aug 24 2010
%H T. Khovanova et al., <a href="http://blog.tanyakhovanova.com/?p=269">The weights puzzle</a>
%H Jon E. Schoenfield, <a href="/A201052/a201052.txt">Excel/VBA macro</a>
%e Numbers n and an example of a subset of {1..n} exhibiting the maximum cardinality c=a(n):
%e 1, {1}
%e 2, {1, 2}
%e 3, {1, 2}
%e 4, {1, 2, 4}
%e 5, {1, 2, 4}
%e 6, {1, 2, 4}
%e 7, {3, 5, 6, 7}
%e 8, {1, 2, 4, 8}
%e 9, {1, 2, 4, 8}
%e 10, {1, 2, 4, 8}
%e 11, {1, 2, 4, 8}
%e 12, {1, 2, 4, 8}
%e 13, {3, 6, 11, 12, 13}
%e 14, {1, 6, 10, 12, 14}
%e 15, {1, 6, 10, 12, 14}
%e 16, {1, 2, 4, 8, 16}
%e 17, {1, 2, 4, 8, 16}
%e 18, {1, 2, 4, 8, 16}
%e For examples of maximum-cardinality subsets at values of n where a(n) > a(n-1), see A096858. - _Jon E. Schoenfield_, Nov 28 2013
%p # is any subset of L uniquely determined by its total weight?
%p iswts := proc(L)
%p local wtset,s,c,subL,thiswt ;
%p # the weight sums are to be unique, so sufficient to remember the set
%p wtset := {} ;
%p # loop over all subsets of weights generated by L
%p for s from 1 to nops(L) do
%p c := combinat[choose](L,s) ;
%p for subL in c do
%p # compute the weight sum in this subset
%p thiswt := add(i,i=subL) ;
%p # if this weight sum already appeared: not a candidate
%p if thiswt in wtset then
%p return false;
%p else
%p wtset := wtset union {thiswt} ;
%p end if;
%p end do:
%p end do:
%p # All different subset weights were different: success
%p return true;
%p end proc:
%p # main sequence: given grams 1 to n, determine a subset L
%p # such that each subset of this subset has a different sum.
%p wts := proc(n)
%p local s,c,L ;
%p # select sizes from n (largest size first) down to 1,
%p # so the largest is detected first as required by the puzzle.
%p for s from n to 1 by -1 do
%p # all combinations of subsets of s different grams
%p c := combinat[choose]([seq(i,i=1..n)],s) ;
%p for L in c do
%p # check if any of these meets the requir, print if yes
%p # and return
%p if iswts(L) then
%p print(n,L) ;
%p return nops(L) ;
%p end if;
%p end do:
%p end do:
%p print(n,"-") ;
%p end proc:
%p # loop for weights with maximum n
%p for n from 1 do
%p wts(n) ;
%p end do: # _R. J. Mathar_, Aug 24 2010
%Y Cf. A005318, A096858, A275972, A276661.
%K nonn,nice
%O 1,2
%A _N. J. A. Sloane_, Nov 26 2011
%E More terms from _Alois P. Heinz_, Nov 27 2011
%E More terms from _Jon E. Schoenfield_, Nov 28 2013
|
