A364132 a(n) is the smallest positive integer such that from the set {1, 2, ..., a(n)} one can choose an increasing sequence (s(1), s(2), ..., s(n)) in which every segment has a unique sum of elements.

1, 2, 4, 5, 7, 10, 12, 13, 15, 18, 21, 24, 25, 29, 30, 33, 36, 38, 41, 47, 50, 52

Offset

1,2

Comments

A segment is a subsequence of consecutive elements.

Erdős asked how fast (the inverse of) this sequence grows.

References

Paul Erdős, Problems and results on combinatorial number theory. III. Number theory day (Proc. Conf., Rockefeller Univ., New York, 1976) (1977), 43-72.

Links

Table of n, a(n) for n=1..22.

Thomas Bloom, Erdős Problem 357.

Example

a(6) = 10, because there exists a 6-element increasing sequence on {1,2,...,10} with unique segment sums, namely (1,2,4,5,8,10) and 10 is the least positive integer with that property. The sums in the segments are: 1, 2, 4, 5, 8, 10 for 1-element segments; 3, 6, 9, 13, 18 for 2-element segments; 7, 11, 17, 23 for 3-element segments; 12, 19, 27 for 4-element segments; 20, 29 for 5-element segments; and 30 for the full set.
a(13) = 25 and the corresponding 13-element subsequence is (1,2,11,15,16,17,18,19,20,21,22,24,25).

Prog

(PARI) a(n, m=2*n) = my(k=1, s=vector(n, i, []), t, u=m, v=vector(n)); while(k>1||v[1]<u-n, t=0; v[k]++; if(k==n, if(v[n]<u, if(!#setintersect(vector(n, i, t=t+v[n+1-i]), s[n]), u=v[n]), k--), if(v[k]<u+k-n, s[k+1]=setunion(vector(k, i, t=t+v[k+1-i]), s[k]); if(#s[k+1]==k*(k+1)/2, v[k+1]=v[k]; k++), k--))); if(u<m, u, a(n, m+4)); \\ Jinyuan Wang, Jul 10 2023

Crossrefs

Cf. A364153 (without monotonicity assumption).

Cf. A276661, A363446.

Sequence in context: A047495 A005653 A188468 * A285251 A325124 A231013

Adjacent sequences: A364129 A364130 A364131 * A364133 A364134 A364135

Keyword

nonn,hard,more

Author

Bartlomiej Pawlik, Jul 10 2023

Extensions

a(14)-a(22) from Jinyuan Wang, Jul 10 2023

Status

approved