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
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
KEYWORD
nonn,base
AUTHOR
Eric Angelini and M. F. Hasler, Oct 28 2019
STATUS
approved