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

%I #43 Apr 25 2024 12:33:36

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

%N 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.

%C This sequence is the main entry for the distinct subset sums problem. See also A201052, A005318, A005255.

%C 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.

%C Lunnon found a(0)-a(8) and J. P. Grossman found a(9).

%C a(10) > 220, with A201052. - _Fausto A. C. Cariboni_, Apr 06 2021

%D Iskander Aliev, Siegel’s lemma and sum-distinct sets, Discrete Comput. Geom. 39 (2008), 59-66.

%D J. H. Conway and R. K. Guy, Solution of a problem of Erdos, Colloq. Math. 20 (1969), p. 307.

%D 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.

%D R. K. Guy, Unsolved Problems in Number Theory, Section C8.

%D Marcin Mucha, Jesper Nederlof, Jakub Pawlewicz, Karol Węgrzycki, Equal-Subset-Sum Faster Than the Meet-in-the-Middle, arXiv:1905.02424

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

%H Tom Bohman, <a href="http://dx.doi.org/10.1090/S0002-9939-96-03653-2">A sum packing problem of Erdős and the Conway-Guy sequence</a>, Proc. AMS 124:12 (1996), pp. 3627-3636.

%H J. H. Conway & R. K. Guy, <a href="/A005318/a005318_2.pdf">Sets of natural numbers with distinct sums</a>, Manuscript.

%H R. K. Guy, <a href="/A003271/a003271.pdf">Letter to N. J. A. Sloane, Apr 1975</a>

%H R. K. Guy, <a href="http://dx.doi.org/10.1016/S0304-0208(08)73500-X">Sets of integers whose subsets have distinct sums</a>, 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.

%H R. K. Guy, <a href="/A005318/a005318_1.pdf">Sets of integers whose subsets have distinct sums</a>, 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)

%H W. F. Lunnon, <a href="http://dx.doi.org/10.1090/S0025-5718-1988-0917837-5">Integer sets with distinct subset-sums</a>, Math. Comp. 50 (1988), pp. 297-320.

%e a(0) = 0: {}

%e a(1) = 1: {1}

%e a(2) = 2: {1, 2}

%e a(3) = 4: {1, 2, 4}

%e a(4) = 7: {3, 5, 6, 7}

%e a(5) = 13: {3, 6, 11, 12, 13}

%e a(6) = 24: {11, 17, 20, 22, 23, 24}

%e a(7) = 44: {20, 31, 37, 40, 42, 43, 44}

%e a(8) = 84: {40, 60, 71, 77, 80, 82, 83, 84}

%e a(9) = 161: {77, 117, 137, 148, 154, 157, 159, 160, 161}

%Y Cf. A005255, A005318, A201052.

%K nonn,hard,more,nice

%O 0,3

%A _Charles R Greathouse IV_ and J. P. Grossman, Sep 11 2016