login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #17 Aug 28 2023 08:21:35

%S 1,2,3,5,6,7,9,10,12,13,14,17,18

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

%C A segment is a subsequence of consecutive elements.

%C Conjecture: There exists C such that a(n) < C*n for every sufficiently large n.

%e a(6) = 7, because there exists a 6-element sequence on the set {1,2,...,7} with unique segment sums: (2,1,7,6,5,4) and 7 is the least positive integer with such property. The sums in the segments are: 2, 1, 7, 6, 5, 4 for 1-element segments; 3, 8, 13, 11, 9 for 2-element segments; 10, 14, 18, 15 for 3-element segments; 16, 19, 22 for 4-element segments; 21, 23 for 5-element segments; and 25 for the full set.

%e a(13) = 18 and the exemplary corresponding 13-element sequence is (1, 6, 15, 8, 11, 9, 16, 17, 18, 13, 14, 10, 2).

%o (PARI) a(n, m=n+6) = my(k=1, s=vector(n, i, []), t, u=m, v=vector(n)); while(k, 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=vecmax(v)), k--), if(v[k]<u, 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]=0; k++), k--))); if(u<m, u, a(n, m+3)); \\ _Jinyuan Wang_, Jul 11 2023

%Y Cf. A276661, A363446, A364132.

%K nonn,hard,more

%O 1,2

%A _Bartlomiej Pawlik_, Jul 11 2023

%E a(10)-a(13) from _Jinyuan Wang_, Jul 11 2023