A201052 - OEIS

%I #60 Dec 23 2024 14:53:42

%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]

%C A276661 is the main entry for the distinct subset sums problem. - _N. J. A. Sloane_, Apr 24 2024

%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="https://web.archive.org/web/*/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