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

Author

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

Keywords

• nonn
• hard
• more
• nice

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

Examples

			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}
		

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

• 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.
• Arun J. Manattu and Aparna Lakshmanan S., Erdős Conjecture and AR-Labeling, arXiv:2502.19182 [math.CO], 2025. See p. 3.

Crossrefs

Cf. A005255, A005318, A201052.