A328861 Concatenation of the permutation of (1, ..., n) that maximizes the minimal sum of increasing concatenations.

1, 21, 132, 4321, 43521, 154632, 6517432, 76518432, 768519432, 98471106532, 1651142910873, 411129101287653, 97864125313121110, 4211113109141287653

Offset

1,2

Comments

a(n) is the concatenation concat(p_1, ..., p_n) of the smallest permutation p of (1, ..., n) such that M(p) = min {S(v); v in C(p)} is maximal, where S(v) is the sum of v's components, and C(p) is the set of all vectors v with increasing components (v_1 < ... < v_k) obtained from p by concatenating some or all adjacent components, for example v = (concat(p_1, p_2), p_3, concat(p_4, ..., p_n)).

Terms were computed by Frank Stevenson, for n < 10 double-checked with given PARI code.

Links

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

E. Angelini, Chunk and sum, personal blog "Cinquante Signes", Oct. 2019

Example

For n = 1, there is only one permutation, p = (1), whence a(1) = 1.
For n = 2, the permutation p = (1,2) yields C(p) = {(1,2), (12)} with M(p) = min {1+2, 12} = 3, while p = (2,1) yields C(p) = {(21)} with M(p) = 21, whence a(n) = concat(2,1) = 21.
For n = 3, the permutation p = (1,3,2) yields C(p) = {(1,32), (132)} with M(p) = 1+32 = 33, and no other permutation yields a larger minimum. (The permutation (2,3,1) would yield the same minimum but comes later.) Therefore a(3) = 132.
a(4) = 4321 with M((4,3,2,1)) = 4+321 = 325.
a(5) = 43521 with M((4,3,5,2,1)) = 43+521 = 564.
a(6) = 154632 with M((1,5,4,6,3,2)) = 1+54+632 = 687.
a(7) = 6517432 with M((6,5,1,7,4,3,2) = 6+51+7432 = 7489.
a(8) = 76518432 with M(p) = 7+651+8432 = 9090.
a(9) = 768519432 with M(p) = 76+851+9432 = 10359
a(10) = 98471106532 with M(p) = 98+471+106532 = 107101.
a(11) = 1651142910873 with M(p) = 1+65+1142+910873 = 912081.
a(12) = 411129101287653 with M(p) = 41+112+910+1287653 = 1288716.
a(13) = 97864125313121110 with M(p) = 97+864+1253+13121110 = 13123324.
a(14) = 4211113109141287653 with M((4,2,1,11,13,10,9,14,12,8,7,6,5,3)) =  42+111+13109+141287653 = 141300915

Prog

(PARI) A328861(n, p=0, m)={ if(!p, (p===0&&n>1)||return(n); my(P); forperm(n, p, m<(m=max(A328861(p[1], Vec(p[^1])), m)) && P=p); fromdigits(Vec(P)), n>=m=fromdigits(p), n*10^#p+m, my(s=A328861(n*10+p[1], p[^1]), t); for(k=logint(n, 10)+1, (#p)\2, n<(t=m\10^(#p-k)) && t<m%10^(#p-k) && return(min(n+A328861(t, p[k+1..-1]), s))); min(n+m, s))} \\ Preliminary version: only for n < 10. - M. F. Hasler, Oct 28 2019

Crossrefs

See A328862 for the values of M(p).

Sequence in context: A110400 A308348 A089369 * A243201 A264554 A125331

Adjacent sequences: A328858 A328859 A328860 * A328862 A328863 A328864

Keyword

nonn,base,more

Author

Eric Angelini and M. F. Hasler, Oct 28 2019

Status

approved