A201052 -id:A201052 - cp's OEIS frontend

A275972 Number of strict knapsack partitions of n.

1, 1, 1, 2, 2, 3, 3, 5, 5, 8, 7, 11, 11, 15, 14, 21, 20, 28, 26, 38, 35, 51, 45, 65, 61, 82, 74, 108, 97, 130, 116, 161, 148, 201, 176, 238, 224, 288, 258, 354, 317, 416, 373, 501, 453, 596, 525, 705, 638, 833, 727, 993, 876, 1148, 1007, 1336, 1199, 1583, 1366, 1816, 1607

Offset: 0

Gus Wiseman, Aug 15 2016

nonn

A strict knapsack partition is a set of positive integers summing to n such that every subset has a different sum.
Unlike in the non-strict case (A108917), the multiset of block-sums of any set partition of a strict knapsack partition also form a strict knapsack partition. If p is a strict knapsack partition of n with k parts, then the upper ideal of p in the poset of refinement-ordered integer partitions of n is isomorphic to the lattice of set partitions of {1,...,k}.
Conjecture: a(n)

			For n=5, there are A000041(5) = 7 sets of positive integers that sum to 5. Four of these have distinct subsets with the same sum: {3,1,1}, {2,2,1}, {2,1,1,1}, and {1,1,1,1,1}.  The other three: {5}, {4,1}, and {3,2}, do not have distinct subsets with the same sum. So a(5) = 3. - _Michael B. Porter_, Aug 17 2016

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..900 (terms 0..101 from Alois P. Heinz, terms 102..500 from Bert Dobbelaere)

Cf. A000009, A000041, A108917, A201052, A335357 (the same for compositions).

sksQ[ptn_]:=And[UnsameQ@@ptn,UnsameQ@@Plus@@@Union[Subsets[ptn]]];
sksAll[n_Integer]:=sksAll[n]=If[n<=0,{},With[{loe=Array[sksAll,n-1,1,Join]},Union[{{n}},Select[Sort[Append[#,n-Plus@@#],Greater]&/@loe,sksQ]]]];
Array[Length[sksAll[#]]&,20]

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.

Original entry on oeis.org

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.

A278044 Length of tribonacci representation of n (cf. A278038).

Original entry on oeis.org

1, 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, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8

Offset: 0

N. J. A. Sloane, Nov 18 2016

For n>=2, n appears A001590(n+2) times. - John Keith, May 23 2022

N. J. A. Sloane, Table of n, a(n) for n = 0..20000
Wolfdieter Lang, The Tribonacci and ABC Representations of Numbers are Equivalent, arXiv preprint arXiv:1810.09787 [math.NT], 2018.

Cf. A278038, A278042, A278043.
Cf. A001590.
Similar to, but strictly different from, A201052.

t[1] = 1; t[2] = 2; t[3] = 4; t[n_] := t[n] = t[n - 1] + t[n - 2] + t[n - 3]; a[0] = 1; a[n_] := Module[{k = 1}, While[t[k] <= n, k++]; k - 1]; Array[a, 100, 0] (* Amiram Eldar, Mar 04 2022 *)

a(n) = A278042(n) + A278043(n).

Showing 1-3 of 3 results.

cp's OEIS Frontend

A275972 Number of strict knapsack partitions of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

A278044 Length of tribonacci representation of n (cf. A278038).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula