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

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

Offset

1,2

Comments

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

Then a(n) = max { M(p); p permutation of (1, ..., n) }. See A328861 for p.

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

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?

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

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)} (no other increasing v can be constructed), 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 (p = (2,3,1) yields the same as 2+31, but comes lexicographically later). Therefore a(3) = 33.
a(4) = M((4,3,2,1)) = 4+321 = 325.
a(5) = M((4,3,5,2,1)) = 43+521 = 564.
a(6) = M((1,5,4,6,3,2)) = 1+54+632 = 687.
a(7) = M((6,5,1,7,4,3,2)) = 6+51+7432 = 7489.
a(8) = M((7,6,5,1,8,4,3,2)) = 7+651+8432 = 9090.
a(9) = M((7,6,8,5,1,9,4,3,2)) = 76+851+9432 = 10359.
a(10) = M((9,8,4,7,1,10,65,3,2)) = 98+471+106532 = 107101.
a(11) = M((1,6,5,11,4,2,9,10,8,7,3)) = 1+65+1142+910873 = 912081.
a(12) = M((4,1,11,2,9,10,12,8,7,6,5,3)) = 41+112+910+1287653 = 1288716.
a(13) = M((9,7,8,6,4,1,2,5,3,13,12,11,10)) = 97+864+1253+13121110 = 13123324.
a(14) = M((4,2,1,11,13,10,9,14,12,8,7,6,5,3)) = 42+111+13109+141287653 = 141300915.
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

Prog

(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.

Crossrefs

See A328861 for the corresponding permutations.

Sequence in context: A032792 A146902 A146910 * A167397 A135595 A082483

Adjacent sequences: A328859 A328860 A328861 * A328863 A328864 A328865

Keyword

nonn,base

Author

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

Status

approved