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

%I #28 Feb 22 2021 23:51:51

%S 1,21,132,4321,43521,154632,6517432,76518432,768519432,98471106532,

%T 1651142910873,411129101287653,97864125313121110,4211113109141287653

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

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

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

%H E. Angelini, <a href="http://cinquantesignes.blogspot.com/2019/10/chunk-sum.html">Chunk and sum</a>, personal blog "Cinquante Signes", Oct. 2019

%e For n = 1, there is only one permutation, p = (1), whence a(1) = 1.

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

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

%e a(4) = 4321 with M((4,3,2,1)) = 4+321 = 325.

%e a(5) = 43521 with M((4,3,5,2,1)) = 43+521 = 564.

%e a(6) = 154632 with M((1,5,4,6,3,2)) = 1+54+632 = 687.

%e a(7) = 6517432 with M((6,5,1,7,4,3,2) = 6+51+7432 = 7489.

%e a(8) = 76518432 with M(p) = 7+651+8432 = 9090.

%e a(9) = 768519432 with M(p) = 76+851+9432 = 10359

%e a(10) = 98471106532 with M(p) = 98+471+106532 = 107101.

%e a(11) = 1651142910873 with M(p) = 1+65+1142+910873 = 912081.

%e a(12) = 411129101287653 with M(p) = 41+112+910+1287653 = 1288716.

%e a(13) = 97864125313121110 with M(p) = 97+864+1253+13121110 = 13123324.

%e a(14) = 4211113109141287653 with M((4,2,1,11,13,10,9,14,12,8,7,6,5,3)) = 42+111+13109+141287653 = 141300915

%o (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

%Y See A328862 for the values of M(p).

%K nonn,base,more

%O 1,2

%A _Eric Angelini_ and _M. F. Hasler_, Oct 28 2019