A276661 -id:A276661 - cp's OEIS frontend

A005318 Conway-Guy sequence: a(n + 1) = 2a(n) - a(n - floor( 1/2 + sqrt(2n) )).

0, 1, 2, 4, 7, 13, 24, 44, 84, 161, 309, 594, 1164, 2284, 4484, 8807, 17305, 34301, 68008, 134852, 267420, 530356, 1051905, 2095003, 4172701, 8311101, 16554194, 32973536, 65679652, 130828948, 261127540, 521203175, 1040311347, 2076449993, 4144588885, 8272623576

Offset: 0

N. J. A. Sloane

Conway and Guy conjecture that the set of k numbers {s_i = a(k) - a(k-i) : 1 <= i <= k} has the property that all its subsets have distinct sums - see Guy's book. These k-sets are the rows of A096858. [This conjecture has apparently now been proved by Bohman. - I. Halupczok (integerSequences(AT)karimmi.de), Feb 20 2006]

J. H. Conway and R. K. Guy, Solution of a problem of Erdos, Colloq. Math. 20 (1969), p. 307.
R. K. Guy, Unsolved Problems in Number Theory, C8.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
M. Wald, Problem 1192, Unequal sums, J. Rec. Math., 15 (No. 2, 1983-1984), pp. 148-149.

Alois P. Heinz, Table of n, a(n) for n = 0..3324 (first 301 terms from T. D. Noe)
Tom Bohman, A sum packing problem of Erdos and the Conway-Guy sequence, Proc. AMS 124, (No. 12, 1996), pp. 3627-3636.
P. Borwein and M. J. Mossinghoff, Newman Polynomials with Prescribed Vanishing and Integer Sets with Distinct Subset Sums, Math. Comp., 72 (2003), 787-800.
J. H. Conway & R. K. Guy, Sets of natural numbers with distinct sums, Manuscript.
R. K. Guy, Letter to N. J. A. Sloane, Apr 1975
R. K. Guy, Sets of integers whose subsets have distinct sums, pp. 141-154 of Theory and practice of combinatorics. Ed. A. Rosa, G. Sabidussi and J. Turgeon. Annals of Discrete Mathematics, 12. North-Holland 1982.
R. K. Guy, Sets of integers whose subsets have distinct sums, pp. 141-154 of Theory and practice of combinatorics. Ed. A. Rosa, G. Sabidussi and J. Turgeon. Annals of Discrete Mathematics, 12. North-Holland 1982. (Annotated scanned copy)
G. Kreweras, Sur quelques problèmes relatifs au vote pondéré [Some problems of weighted voting], Math. Sci. Humaines No. 84 (1983), 45-63.
G. Kreweras, Alvarez Rodriguez, Miguel-Angel, Pondération entière minimale de N telle que pour tout k toutes les k-parties de N aient des poids distincts, [Minimal integer weighting of N such that for any k all the k-subsets of N have unequal weights] C. R. Acad. Sci. Paris Ser. I Math. 296 (1983), no. 8, 345-347.
G. Kreweras, Alvarez Rodriguez, Miguel-Angel, Pondération entière minimale de N telle que pour tout k toutes les k-parties de N aient des poids distincts, [Minimal integer weighting of N such that for any k all the k-subsets of N have unequal weights], C. R. Acad. Sci. Paris Ser. I Math. 296 (1983), no. 8, 345-347. (Annotated scanned copy)
W. F. Lunnon, Integer sets with distinct subset-sums, Math. Comp. 50 (1988), 297-320.
M. Wald & N. J. A. Sloane, Correspondence and Attachment, 1987

A276661 is the main entry for the distinct subset sums problem.

Cf. A037254, A096858, A096796, A096824, A205744, A206239, A083920, A003056.

a005318 n = a005318_list !! n
a005318_list = 0 : 1 : zipWith (-)
   (map (* 2) $ tail a005318_list) (map a005318 a083920_list)
-- Reinhard Zumkeller, Feb 12 2012

a[n_] := a[n] = 2*a[n-1] - a[n - Floor[Sqrt[2]*Sqrt[n-1] + 1/2] - 1]; a[0]=0; a[1]=1; Table[a[n], {n, 0, 33}] (* Jean-François Alcover, May 15 2013 *)

a(n)=if(n<=1,n==1,2*a(n-1)-a(n-1-(sqrtint(8*n-15)+1)\2))

A=[]; /* This is the program above with memoization. */
a(n)=if(n<3, return(n)); if(n>#A, A=concat(A,vector(n-#A)), if(A[n], return(A[n]))); A[n]=2*a(n-1)-a(n-1-(sqrtint(8*n-15)+1)\2) \\ Charles R Greathouse IV, Sep 09 2016

from sympy import sqrt, floor
def a(n): return n if n<2 else 2*a(n - 1) - a(n - floor(sqrt(2)*sqrt(n - 1) + 1/2) - 1) # Indranil Ghosh, Jun 03 2017

a(n+1) = 2*a(n)-A205744(n), A205744(n) = a(A083920(n)), A083920(n) = n - A002024(n). - N. J. A. Sloane, Feb 11 2012

More terms from Larry Reeves (larryr(AT)acm.org), Sep 21 2000

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.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane, Nov 26 2011

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

			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

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

Cf. A005318, A096858, A275972, A276661.

# 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

More terms from Alois P. Heinz, Nov 27 2011

More terms from Jon E. Schoenfield, Nov 28 2013

A259544 Minimum greatest integer in a set of n positive integers whose nonempty subsets all have distinct arithmetic means.

Original entry on oeis.org

1, 2, 4, 7, 16, 32, 75, 169, 396

Offset: 1

Javier Múgica, Jun 30 2015

Let a set of integers be called "of different average" if any two distinct, nonempty subsets of it have distinct arithmetic means. E.g., the set {1,2,5} is of different average because 1 != 2 != 5 != (1+2)/2 != (1+5)/2 != (2+5)/2 != (1+2+5)/3.
In order for a set to be of different average it is obvious that all its elements must be different. Also, if a set is of different average and a constant k is added to all the terms, the resulting set will also be of different average. Because of this, in order to study such sets it is convenient to select an arbitrary first element, say 1. Therefore the terms of this sequence are defined as: the least a_n such that the set 1 = a_1 < a_2 < a_3 < ... < a_n is of different average.
The set {1,2,4,...,2^(n-1)} satisfies that any natural number can only be written in one way as a sum of elements of the set (each element being allowed to enter only once into the sum), so it is a good candidate as a different average set, and it is so up to 1,2,4,8,16,32, but it fails for 1,...,64, since (4+8+16+64)/4 = (1+2+16+32+64)/5 = 23. Other than by brute force, this can easily be found by noting that the number 23, written in binary notation: 10111, has four ones, hence 4 times the number obviously has four ones too, while 5 times the number = 1110011 has five ones, and those are the subsets.
Conjecture: The only term that is < 2^(n-1) is a(4)=7.
It may be proved that, for n>1, a(n) < 4^(n-1):
Suppose we already have a set of n-1 numbers satisfying the property. If an element a_n is added, 2^n possible sets can be formed, hence fewer than 2^n * 2^n / 2 = 4^n/2 pairs of sets. If a certain value of a_n gives the same average for two such subsets, any other value will yield different averages. It is easy to see that only half the pairs need be considered; hence there is at least one value of a_n < 4^(n-1) that yields different averages for all pairs of subsets.
If more set pairs are excluded, viz. sets that both include a_n and that either have the same number of elements (because the set a_1,...,a_(n-1) is presumed to already satisfy the property) or the set having more elements has a lower average than the other with a_n excluded from both (a_n will eventually be greater than all the other a_i; if not, interchange the a_n found with one of the a_i and "run" the reasoning again), the 4^(n-1) bound may be improved slightly. Note that the latter property of set pairs is transitive, in the sense that if any such pair satisfies the property, the pair formed by adding a_n to both sets also satisfies the property.
What is lim_sup a(n)^(1/n)? The upper bound above proves it is <=4.
Conjecture: lim a(n)/2^n = infinity. (Note that this is weaker than lim_inf a(n)^(1/n) > 2.)
Does lim a(n)^(1/n) exist?
A259545 provides the values of N such that all k>=N can be the greatest element of a different average set of n elements.
A set of different average with n elements has A001405(n) ~ 2^n * sqrt(2/(Pi*n)) subsets of size floor(n/2) which must have different sums, so the largest such sum is at least A001405(n), and thus the largest element is at least A001405(n)*2/n. This shows that lim inf a(n)^(1/n) >= 2. - Robert Israel, Aug 02 2015
a(10) <= 1303, as shown by the example {1, 43, 151, 235, 421, 981, 1093, 1161, 1266, 1303}. - Robert Israel, Jan 20 2016
a(10) <= 1252, as shown by the example {1, 76, 181, 211, 293, 727, 1126, 1196, 1216, 1252}. - Robert Israel, Jan 25 2016
Changing this sequence's requirement of "distinct arithmetic means" to "distinct sums" gives sequence A276661. - Jon E. Schoenfield, Nov 05 2016

			The 15 averages of 1 to 4 elements in the set {1, 2, 5, 7} (or alternately {1, 3, 6, 7}) are all different, so a(4) <= 7. There are no such sets of 4 positive integers with all members less than 7, so in fact a(4) = 7.
The set providing the last term at present in the sequence, viz. 396 = a(9), is {1, 13, 21, 51, 151, 327, 336, 342, 396} (or, by symmetry, {1, 55, 61, 70, 246, 346, 376, 384, 396}).

Javier Múgica, medias.c. A program for finding a(n). medias10.c. The same as the previous program, except that set up for checking a particular value for 10-element different average sets.

Cf. A259545, A227590, A227588, A276661.

a(n) < 4^(n-1) for n > 1, see comments.

a(9) from Javier Múgica, Nov 12 2015

A363446 Increasing sequence such that a(1) = 1 and a(n) is the least integer such that every segment of the sequence a(1),a(2),...,a(n) has a unique sum of elements.

Original entry on oeis.org

1, 2, 4, 5, 8, 10, 14, 21, 25, 26, 28, 31, 36, 38, 55, 56, 66, 68, 88, 91, 92, 94, 102, 125, 127, 136, 140, 158, 162, 164, 180, 182, 201, 217, 220, 226, 228, 240, 241, 259, 261, 275, 314, 331, 337, 342, 356, 366, 380, 391, 408, 432, 441, 444, 456, 469, 478, 548, 560, 565, 574, 577, 580, 586, 628, 639, 696, 701, 707, 730, 731, 732, 733, 752, 759, 773, 849, 877, 890, 922

Offset: 1

Bartlomiej Pawlik, Jul 09 2023

nonn

A segment is a subsequence given by consecutive elements.

			The smallest candidate for a(3) is 3, but the sequence (1,2,3) has two segments with equal sums, namely (1,2) and (3). The next candidate is 4 and every segment of the sequence (1,2,4) has a unique sum, so a(3) = 4.

If we omit the condition that {a(n)} is increasing, we get A101274.

Cf. A276661.

A349777 Lexicographically first sequence of positive integers such that all disjoint equivalent sets of K terms have distinct sums for 1 <= K <= 4.

Original entry on oeis.org

1, 2, 3, 5, 8, 14, 25, 45, 85, 162, 310, 595, 1107, 2052, 3515, 5925, 9798, 16169, 23295, 34303, 53259, 72215, 112624, 153552, 198523, 283570, 370114, 497383, 700022, 840817, 1145415, 1398434, 1717972, 2279969, 2819186, 3436864, 4299205, 5239007, 6335442, 7650495, 9219214

Offset: 1

Santanu Banerjee, Nov 29 2021

nonn

Gleb Ivanov, Python program.

Cf. A011185 (k=1..2), A036241 (k=1..3).

A005318 and A276661 are similar sequences.

a={};k=1;Do[While[(t=1;While[t<=4&&DuplicateFreeQ[Total/@Subsets[Join[a,{k}],{t}]],t++];t)<=4,k++];AppendTo[a,k];Print@k,30] (* Giorgos Kalogeropoulos, Dec 02 2021 *)

Python
```
# See links.
```

a(13)-a(26) from Alois P. Heinz, Dec 01 2021

a(27)-a(41) from Gleb Ivanov, Dec 02 2021

A364132 a(n) is the smallest positive integer such that from the set {1, 2, ..., a(n)} one can choose an increasing sequence (s(1), s(2), ..., s(n)) in which every segment has a unique sum of elements.

Original entry on oeis.org

1, 2, 4, 5, 7, 10, 12, 13, 15, 18, 21, 24, 25, 29, 30, 33, 36, 38, 41, 47, 50, 52

Offset: 1

Bartlomiej Pawlik, Jul 10 2023

A segment is a subsequence of consecutive elements.

			a(6) = 10, because there exists a 6-element increasing sequence on {1,2,...,10} with unique segment sums, namely (1,2,4,5,8,10) and 10 is the least positive integer with that property. The sums in the segments are: 1, 2, 4, 5, 8, 10 for 1-element segments; 3, 6, 9, 13, 18 for 2-element segments; 7, 11, 17, 23 for 3-element segments; 12, 19, 27 for 4-element segments; 20, 29 for 5-element segments; and 30 for the full set.
a(13) = 25 and the corresponding 13-element subsequence is (1,2,11,15,16,17,18,19,20,21,22,24,25).

Cf. A364153 (without monotonicity assumption).

Cf. A276661, A363446.

a(n, m=2*n) = my(k=1, s=vector(n, i, []), t, u=m, v=vector(n)); while(k>1||v[1]Jinyuan Wang, Jul 10 2023

a(14)-a(22) from Jinyuan Wang, Jul 10 2023

A364153 a(n) is the smallest positive integer such that from the set {1, 2, ..., a(n)} one can choose a sequence (s(1), s(2), ..., s(n)) in which every segment has a unique sum.

Original entry on oeis.org

1, 2, 3, 5, 6, 7, 9, 10, 12, 13, 14, 17, 18

Offset: 1

Bartlomiej Pawlik, Jul 11 2023

A segment is a subsequence of consecutive elements.

Conjecture: There exists C such that a(n) < C*n for every sufficiently large n.

			a(6) = 7, because there exists a 6-element sequence on the set {1,2,...,7} with unique segment sums: (2,1,7,6,5,4) and 7 is the least positive integer with such property. The sums in the segments are: 2, 1, 7, 6, 5, 4 for 1-element segments; 3, 8, 13, 11, 9 for 2-element segments; 10, 14, 18, 15 for 3-element segments; 16, 19, 22 for 4-element segments; 21, 23 for 5-element segments; and 25 for the full set.
a(13) = 18 and the exemplary corresponding 13-element sequence is (1, 6, 15, 8, 11, 9, 16, 17, 18, 13, 14, 10, 2).

Cf. A276661, A363446, A364132.

a(n, m=n+6) = my(k=1, s=vector(n, i, []), t, u=m, v=vector(n)); while(k, t=0; v[k]++; if(k==n, if(v[n]Jinyuan Wang, Jul 11 2023

a(10)-a(13) from Jinyuan Wang, Jul 11 2023

cp's OEIS Frontend

A005318 Conway-Guy sequence: a(n + 1) = 2a(n) - a(n - floor( 1/2 + sqrt(2n) )).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Python

Formula

Extensions

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Extensions

A259544 Minimum greatest integer in a set of n positive integers whose nonempty subsets all have distinct arithmetic means.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A363446 Increasing sequence such that a(1) = 1 and a(n) is the least integer such that every segment of the sequence a(1),a(2),...,a(n) has a unique sum of elements.

Views

Author

Keywords

Comments

Examples

Crossrefs

A349777 Lexicographically first sequence of positive integers such that all disjoint equivalent sets of K terms have distinct sums for 1 <= K <= 4.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Python

Extensions

A364132 a(n) is the smallest positive integer such that from the set {1, 2, ..., a(n)} one can choose an increasing sequence (s(1), s(2), ..., s(n)) in which every segment has a unique sum of elements.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Extensions

A364153 a(n) is the smallest positive integer such that from the set {1, 2, ..., a(n)} one can choose a sequence (s(1), s(2), ..., s(n)) in which every segment has a unique sum.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Extensions