A328862 - OEIS

%I #17 Oct 29 2019 11:11:47

%S 1,21,33,325,564,687,7489,9090,10359,107101,912081,1288716,13123324,

%T 141300915

%N Maximum of the smallest sum of increasing concatenations of a permutation of {1, ..., n}.

%C For a permutation p of (1, ..., n), let M(p) = min { S(v); v in C(p) }, 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 Then a(n) = max { M(p); p permutation of (1, ..., n) }. See A328861 for p.

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

%C One could use "nondecreasing" instead of "increasing" in the definition of C(p). At which point this would yield the first different a(n), if any?

%C It appears that a(n) is within an order of magnitude of the square root of the concatenation of {1, ..., n}. The permutation p (cf. A328861(n)) can probably be constructed "from right to left" by concatenating roughly half of the numbers in {1,...,n} in some order to yield the last term in S(v), i.e., last component of v, then preceding terms by decreasing the number of digits while making sure that the following term(s) cannot be split up otherwise. The value of a(n) = M(p) is then very close to the last component of v. - _M. F. Hasler_, Oct 29 2019

%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)} (no other increasing v can be constructed), 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 (p = (2,3,1) yields the same as 2+31, but comes lexicographically later). Therefore a(3) = 33.

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

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

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

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

%e a(8) = M((7,6,5,1,8,4,3,2)) = 7+651+8432 = 9090.

%e a(9) = M((7,6,8,5,1,9,4,3,2)) = 76+851+9432 = 10359.

%e a(10) = M((9,8,4,7,1,10,65,3,2)) = 98+471+106532 = 107101.

%e a(11) = M((1,6,5,11,4,2,9,10,8,7,3)) = 1+65+1142+910873 = 912081.

%e a(12) = M((4,1,11,2,9,10,12,8,7,6,5,3)) = 41+112+910+1287653 = 1288716.

%e a(13) = M((9,7,8,6,4,1,2,5,3,13,12,11,10)) = 97+864+1253+13121110 = 13123324.

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

%e As an example for how to construct this, consider the 7 numbers (14,12,8,7,6,5,3) with concatenation 141287653. If the preceding term is larger than 1412, then this cannot be split up. This is the case for concat(13,10,9) = 13109. The whole cannot be split up as 1310+91412+87653 (last term too small), but to prevent splitting up into 13+109+... the preceding term must be larger than 13. This is true for concat(1,11) (or 11,1), and so on. Restricting the initial choice to a permutation of 7 among 14 narrows the search space compared to considering all permutations of [1..14] and possible increasing concatenations. - _M. F. Hasler_, Oct 29 2019

%o (PARI) A328862(n,p=0,m=1)={ if(!p, n>1 && forperm(n,p, m=max(A328862(p[1], Vec(p[^1])),m)); m, n>=m=fromdigits(p), n*10^logint(m*10,10)+m, n<p[1] && !sum(i=2,#p,p[i-1]>p[i]), n+vecsum(p), my(t); for(k=logint(n,10)+1,(#p)\2, (t=m\10^(#p-k))>n && t<m%10^(#p-k) && return(min(A328862(n*10+p[1],p[^1]), A328862(t, p[k+1..-1])+n))); min(A328862(n*10+p[1],p[^1]),n+m))} \\ Preliminary version: only for n < 10.

%Y See A328861 for the corresponding permutations.

%K nonn,base

%O 1,2

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