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,3

Comments

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

References

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

Links

Table of n, a(n) for n=0..9.

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

Example

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}

Crossrefs

Cf. A005255, A005318, A201052.

Sequence in context: A000073 A255069 A160254 * A005318 A102111 A224704

Adjacent sequences: A276658 A276659 A276660 * A276662 A276663 A276664

Keyword

nonn,hard,more,nice

Author

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

Status

approved