A005255 -id:A005255 - cp's OEIS frontend

A276661 Least k such that there is a set S in {1, 2, ..., k} with n elements and the property that each of its subsets has a distinct sum.

0, 1, 2, 4, 7, 13, 24, 44, 84, 161

Offset: 0

Charles R Greathouse IV and J. P. Grossman, Sep 11 2016

This sequence is the main entry for the distinct subset sums problem. See also A201052, A005318, A005255.
The Conway-Guy sequence A005318 is an upper bound. Lunnon showed that a(67) < 34808838084768972989 = A005318(67), and Bohman improved the bound to a(67) <= 34808712605260918463.
Lunnon found a(0)-a(8) and J. P. Grossman found a(9).
a(10) > 220, with A201052. - Fausto A. C. Cariboni, Apr 06 2021

			a(0) = 0: {}
a(1) = 1: {1}
a(2) = 2: {1, 2}
a(3) = 4: {1, 2, 4}
a(4) = 7: {3, 5, 6, 7}
a(5) = 13: {3, 6, 11, 12, 13}
a(6) = 24: {11, 17, 20, 22, 23, 24}
a(7) = 44: {20, 31, 37, 40, 42, 43, 44}
a(8) = 84: {40, 60, 71, 77, 80, 82, 83, 84}
a(9) = 161: {77, 117, 137, 148, 154, 157, 159, 160, 161}

Iskander Aliev, Siegel’s lemma and sum-distinct sets, Discrete Comput. Geom. 39 (2008), 59-66.
J. H. Conway and R. K. Guy, Solution of a problem of Erdos, Colloq. Math. 20 (1969), p. 307.
Dubroff, Q., Fox, J., & Xu, M. W. (2021). A note on the Erdos distinct subset sums problem. SIAM Journal on Discrete Mathematics, 35(1), 322-324.
R. K. Guy, Unsolved Problems in Number Theory, Section C8.
Marcin Mucha, Jesper Nederlof, Jakub Pawlewicz, Karol Węgrzycki, Equal-Subset-Sum Faster Than the Meet-in-the-Middle, arXiv:1905.02424
Stefan Steinerberger, Some remarks on the Erdős Distinct subset sums problem, International Journal of Number Theory, 2023 , #19:08, 1783-1800 (arXiv:2208.12182).

Thomas Bloom, Problem 1, Erdős Problems.
Tom Bohman, A sum packing problem of Erdős and the Conway-Guy sequence, Proc. AMS 124:12 (1996), pp. 3627-3636.
J. H. Conway and 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)
W. F. Lunnon, Integer sets with distinct subset-sums, Math. Comp. 50 (1988), pp. 297-320.
Arun J. Manattu and Aparna Lakshmanan S., Erdős Conjecture and AR-Labeling, arXiv:2502.19182 [math.CO], 2025. See p. 3.
Terence Tao, Erdős problem database, see entry no. 1.

Cf. A005255, A005318, A201052.

A037254 Triangle read by rows: T(n,k) (n >= 1, 1 <= k< = n) gives number of non-distorting tie-avoiding integer vote weights.

Original entry on oeis.org

1, 1, 2, 2, 3, 4, 3, 5, 6, 7, 6, 9, 11, 12, 13, 11, 17, 20, 22, 23, 24, 22, 33, 39, 42, 44, 45, 46, 42, 64, 75, 81, 84, 86, 87, 88, 84, 126, 148, 159, 165, 168, 170, 171, 172, 165, 249, 291, 313, 324, 330, 333, 335, 336, 337, 330, 495, 579, 621, 643, 654, 660, 663, 665

Offset: 1

N. J. A. Sloane

T(n,1) = T(n,floor(n/2)+1) = A002083(n+2). - Reinhard Zumkeller, Nov 18 2012

			Triangle:
  1;
  1,  2;
  2,  3,  4;
  3,  5,  6,  7;
  6,  9, 11, 12, 13;
  ...

Author?, Solution to Board of Directors Problem, J. Rec. Math., 9 (No. 3, 1977), 240.
T. V. Narayana, Lattice Path Combinatorics with Statistical Applications. Univ. Toronto Press, 1979, pp. 100-101.

Reinhard Zumkeller, Rows n = 1..150 of triangle, flattened
M. Klamkin, ed., Problems in Applied Mathematics: Selections from SIAM Review, SIAM, 1990; see pp. 122-123.
G. Kreweras, Sur quelques problèmes relatifs au vote pondéré, [Some problems of weighted voting], Math. Sci. Humaines No. 84 (1983), 45-63.
B. E. Wynne & N. J. A. Sloane, Correspondence, 1976-84
B. E. Wynne & T. V. Narayana, Tournament configuration, weighted voting, and partitioned catalans, Preprint.
Bayard Edmund Wynne, and T. V. Narayana, Tournament configuration and weighted voting, Cahiers du bureau universitaire de recherche opérationnelle, 36 (1981): 75-78.
Solution to Board of Directors Problem, J. Rec. Math., 9 (No. 3, 1977), 240. (Annotated scanned copy)

Row sums give A005254. A002083 is a column. See also A005318, A096858.

Cf. A005255, A062178.

a037254 n k = a037254_tabl !! (n-1) !! (k-1)
a037254_row n = a037254_tabl !! (n-1)
a037254_tabl = map fst $ iterate f ([1], drop 2 a002083_list) where
   f (row, (x:xs)) = (map (+ x) (0 : row), xs)
-- Reinhard Zumkeller, Nov 18 2012

a[1, 1] = 1; a[n_, 1] := a[n, 1] = a[n - 1, Floor[(n + 1)/2]]; a[n_, k_ /; k > 1] := a[n, k] = a[n, 1] + a[n - 1, k - 1]; A037254 = Flatten[ Table[ a[n, k], {n, 1, 11}, {k, 1, n}]] (* Jean-François Alcover, Apr 03 2012, after given recurrence *)

def T(n, k):
    if k==1:
        if n==1: return 1
        else: return T(n - 1, (n + 1)//2)
    return T(n, 1) + T(n - 1, k - 1)
for n in range(1, 12): print([T(n, k) for k in range(1, n + 1)]) # Indranil Ghosh, Jun 03 2017

T(1,1) = 1;
T(n,1) = T(n-1, floor((n+1)/2));
T(n,k) = T(n,1) + T(n-1,k-1) for k > 1.

More terms from (and formula corrected by) James Sellers, Feb 04 2000

A062178 a(n+1) = 2a(n)-a([n/2]) starting with a(0)=0 and a(1)=1.

Original entry on oeis.org

0, 1, 2, 3, 5, 8, 14, 25, 47, 89, 173, 338, 668, 1322, 2630, 5235, 10445, 20843, 41639, 83189, 166289, 332405, 664637, 1328936, 2657534, 5314400, 10628132, 21254942, 42508562, 85014494, 170026358, 340047481, 680089727, 1360169009, 2720327573

Offset: 0

Henry Bottomley, Jun 12 2001

nonn

As partial sum of Narayana-Zidek-Capell numbers A002083, this is the number of words beginning with 1, with sum of integers <=n, in the sequence 1, 11, 111, 112, 1111, 1112, 1113, 1121, 1122, 1123, 1124, 11111, 11112, 11113, 11114, 11121, 11122, 11123, 11124, 11125, 11131, 11132, 11133, 11134, 11135, 11136, where any positive integer, in any word, is <= the sum of the preceding integers.
The subsequence of primes in this partial sum begins: 2, 3, 5, 47, 89, 173, 166289. [From Jonathan Vos Post, Feb 17 2010]
For n > 0: a(n) = A005255(n-1) + 1. - Reinhard Zumkeller, Nov 18 2012

			a(7)=2a(6)-a(3)=2*14-3=25. a(8)=2a(7)-a(3)=2*25-3=47. a(9)=2a(8)-a(4)=2*47-5=89.

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000

a062178 n = a062178_list !! (n-1)
a062178_list = scanl (+) 0 a002083_list
-- Reinhard Zumkeller, Nov 18 2012

a(n) =a(n-1)+A002083(n).

A242729 Decimal expansion of the Atkinson-Negro-Santoro constant, a constant associated with Erdős' sum-distinct set constant.

Original entry on oeis.org

3, 1, 6, 6, 8, 4, 1, 7, 3, 6, 5, 2, 7, 0, 5, 8, 2, 0, 2, 1, 8, 3, 5, 6, 5, 7, 2, 3, 0, 8, 2, 8, 8, 3, 2, 9, 6, 4, 6, 6, 7, 9, 9, 5, 4, 3, 9, 1, 7, 0, 8, 3, 4, 4, 6, 0, 2, 2, 0, 0, 5, 6, 8, 8, 2, 0, 2, 0, 0, 1, 4, 0, 2, 1, 2, 6, 1, 4, 6, 8, 2, 5, 6, 5, 6, 5, 0, 1, 7, 8, 9, 8, 2, 5, 5, 0, 4, 0, 0, 4

Offset: 0

Jean-François Alcover, May 21 2014

			0.3166841736527058202183565723...

Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, Section 2.28, p. 189.

W. F. Lunnon, Integer sets with distinct subset-sums, Math. Comp. 50 (1988), 297-320.

Cf. A002083, A005255.

digits = 100; Clear[u, s]; u[n_] := u[n] = 2 u[n-1] - u[n-1 - Floor[(n-1)/2 + 1]]; u[0] = 0; u[1] = 1; s[k_] := s[k] = u[k]/2^k // N[#, digits + 5] &; s[dk = 100]; s[k = 2*dk]; While[RealDigits[s[k], 10, digits] != RealDigits[s[k - dk], 10, digits], Print["k = ", k]; k = k + dk]; RealDigits[s[k], 10, digits] // First

A180459 Sampling n numbers between 1 and a(n)-1, you are guaranteed to always find two subsets whose sums are equal.

Original entry on oeis.org

3, 5, 8, 13, 21, 36, 61, 107, 191, 347, 636, 1177, 2192, 4104, 7718, 14572, 27603, 52439, 99875, 190661, 364733, 699063, 1342190, 2581123, 4971040, 9586994, 18512804, 35791409, 69273681, 134217744, 260301065, 505290287, 981706828

Offset: 3

Marc Leotard (m.leotard(AT)ephec.be), Sep 06 2010

nonn

Related to sequence A005255. We look for the largest number m(n) such that, in ANY sample of n numbers from 1 to m, there are always two subsets whose sums are equal.
A005255 gives an upper bound for the lowest number M for which the condition does not hold.
While searching for the solution, I used a "pigeonhole"-type argument to derive a lower bound for M. In a n-elements sample in {1,...,m}, there are S = 2^n - 2 nontrivial subsets (i.e. excluding the empty and the full); the maximum possible "subsum" is P = (m) + (m-1) + ... + (m-n+1) = nm - n(n-1)/2. By the pigeonhole principle, if S > P, there must be at least two subsums that are equal.
This condition S>P is rewritten m > [2^n - 2 + n(n-1)/2]/n , yielding the above sequence.
I do not know what are the exact m(n), between the upper and lower limits.
I would not have mentioned it, were it not for its similarity with Fibonacci in the first terms.

			Example for n=6 : in a 6-elements sample, there are S = 2^6 - 2 = 62 nontrivial subsets; the maximum possible "subsum" is P = (m) + (m-1) + ... + (m-5) = 6m - 6*5/2 = 6m - 15. With m = a(6) = 13, P = 63 : this is the lowest value of m for which the argument S>P is not working.

f[n_] := Ceiling[(2^n + n (n - 1)/2 - 2)/n]; Array[f, 30, 3] (* Robert G. Wilson v, Sep 07 2010 *)

For n>=3, a(n)= [ 2^n - 2 + n(n-1)/2 ] / n rounded up.

More terms from Robert G. Wilson v, Sep 07 2010

A242730 Decimal expansion of the Conway-Guy constant, a constant associated with Erdős' sum-distinct set constant.

Original entry on oeis.org

2, 3, 5, 1, 2, 5, 2, 8, 4, 8, 1, 1, 1, 7, 4, 8, 6, 5, 6, 3, 5, 5, 8, 8, 1, 7, 4, 3, 9, 1, 8, 7, 9, 0, 0, 9, 8, 8, 0, 9, 8, 4, 5, 1, 9, 5, 8, 3, 5, 2, 9, 5, 9, 8, 5, 8, 2, 6, 7, 7, 9, 6, 6, 3, 1, 6, 7, 0, 3, 1, 9, 0, 5, 1, 3, 7, 1, 3, 2, 4, 8, 7, 4, 7, 1, 4, 0, 9, 0, 0, 0, 0, 1, 5, 0, 0, 3, 1, 1, 7

Offset: 0

Jean-François Alcover, May 21 2014

			0.23512528481117486563558817439187900988...

J. H. Conway and R. K. Guy, “Sets of Natural Numbers with Distinct Sums,” Notices Amer. Math. Soc., vol. 15, 1968.
Steven R. Finch, Mathematical Constants, Cambridge University Press, 2003, Section 2.28, p. 189.

W. F. Lunnon, Integer sets with distinct subset-sums, Math. Comp. 50 (1988), 297-320.

Cf. A002083, A005255.

digits = 100; Clear[v, s]; v[n_] := v[n] = 2*v[n-1] - v[n-1 - Floor[1/2 + Sqrt[2*(n-1)]]]; v[0] = 0; v[1] = 1; s[k_] := s[k] = v[k]/2^k // N[#, digits + 5] &; s[dk = 250]; s[k = 2*dk]; While[RealDigits[s[k], 10, digits] != RealDigits[s[k - dk], 10, digits],  Print["k = ", k]; k = k + dk]; RealDigits[s[k], 10, digits] // First

cp's OEIS Frontend

A276661 Least k such that there is a set S in {1, 2, ..., k} with n elements and the property that each of its subsets has a distinct sum.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A037254 Triangle read by rows: T(n,k) (n >= 1, 1 <= k< = n) gives number of non-distorting tie-avoiding integer vote weights.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

Python

Formula

Extensions

A062178 a(n+1) = 2a(n)-a([n/2]) starting with a(0)=0 and a(1)=1.

Views

Author

Keywords

Comments

Examples

Links

Programs

Haskell

Formula

A242729 Decimal expansion of the Atkinson-Negro-Santoro constant, a constant associated with Erdős' sum-distinct set constant.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

A180459 Sampling n numbers between 1 and a(n)-1, you are guaranteed to always find two subsets whose sums are equal.

Views

Author

Keywords

Comments

Examples

Programs

Mathematica

Formula

Extensions

A242730 Decimal expansion of the Conway-Guy constant, a constant associated with Erdős' sum-distinct set constant.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica