login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 3
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, 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, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8 (list; graph; refs; listen; history; text; internal format)
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]

LINKS

Jon E. Schoenfield, Table of n, a(n) for n = 1..120

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

Cf. A005318, A096858, A275972, A276661.

Sequence in context: A085727 A143442 A137300 * A278044 A255121 A095791

Adjacent sequences:  A201049 A201050 A201051 * A201053 A201054 A201055

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified September 25 18:05 EDT 2017. Contains 292499 sequences.