cp's OEIS Frontend

A201052 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.

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