[seqfan] Re: A simple looking sequence is spontaneously breaking its monotony

[M. F. Hasler]

I can confirm these values and  a(n+1) < a(n)  for  n = 52, 76, ... (see
below).
The function can be written in PARI/GP as follows:

TS(n, K=0) = { my(a=A001055(n)); while(n>2*K+=1, a=max(
A001055(K)+TS(n-K,K), a) ); a }

vector(90,n,TS(n))
% = [1, 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9, 9,
10, 10, 10, 11, 11, 11, 12, 12, 12, 13, 13, 13, 14, 14, 14, 14, 15, 15, 15,
16, 16, 16, 17, 17, 17, 18, 18, 18, 19, 18, 19, 19, 19, 20, 20, 20, 21, 21,
21, 21, 22, 22, 22, 23, 23, 23, 24, 24, 24, 25, 25, 25, 26, 25, 26, 26, 26,
27, 27, 27, 27, 28, 28, 28, 28, 28, 29]

[i | i<-[2..#%],%[i]<%[i-1]]  \\ indices where a(n) > a(n-1)
% = [53, 77]

Due to the recursion, the above function becomes slow when n approaches
100. With memoization it remains fast enough up to n=500 at least.

M=Map(); TS(n, K=0) = { if( n < 2*K+3, A001055(n), mapisdefined(M,[n,K]),
mapget(M,[n,K]), my(a=A001055(n));
 for( k1 = K+1, (n-1)\2, a=max( A001055(k1) + TS(n-k1, k1), a) );
mapput(M,[n,K],a); a) }

[n | n <- [2..500], TS(n) < TS(n-1)]  \\ indices where a(n) > a(n-1)

% = [53, 77, 113, 125, 161, 233, 322, 327, 329, 334, 466, 471, 473, 478]

It seems that these indices tend to come in groups :
 {53, 77}, {113, 125}, {322, 327, 329, 334}, {466, 471, 473, 478}

(But I don't know whether this goes on, and I didn't think about an
explanation ...)

- Maximilian

On Tue, Oct 26, 2021 at 4:09 AM Thomas Scheuerle wrote:

> Split n into a sum n = k1+k2+..km such that a(n) =
> A001055(k1)+...A001055(km) becomes maximal.
> A001055(km)  is the number of ways of factoring km with all factors
> greater than 1.
>
> There are yet two cases known to me where  a(n+1) < a(n) this is  at n =
> 52 and 76.
>
> There may be several sums for each n, which reach a(n), but some examples
> of the lexicographically earliest are found here:
>
>   n = k1+k2+..+km          A001055(k1)+...A001055(km)          = a(n)
> n's for prefixes in the sum
>
> --------------------------------------------------------------------------------------------------------
>   1 = 1                             1                          = 1
>   2 = 2                             1                          = 1
>   3 = 1+2                           1+1                        = 2       1
>   4 = 1+3                           1+1                        = 2       1
>   5 = 1+4                           1+2                        = 3       1
>   6 = 1+2+3                         1+1+1                      = 3
>  1;3
>   7 = 1+2+4                         1+1+1                      = 4
>  1;3
>   8 = 1+3+4                         1+1+2                      = 4
>  1;4
>   9 = 2+3+4                         1+1+2                      = 4       2
>  10 = 1+2+3+4                       1+1+1+2                    = 5
>  1;3;6
>  11 = 1+4+6                         1+2+2                      = 5
>  1;5
>  12 = 1+2+4+5                       1+1+2+1                    = 5
>  1;3;7
>  13 = 1+2+4+6                       1+1+2+2                    = 6
>  1;3;7
>  14 = 1+3+4+6                       1+1+2+2                    = 6
>  1;4;8
>  15 = 1+2+4+8                       1+1+2+3                    = 7
>  1;3;7;
>  16 = 1+2+3+4+6                     1+1+1+2+2                  = 7
>  1;3;6;10
>  17 = 2+3+4+8                       1+1+2+3                    = 7
>  2;9
>  18 = 1+2+3+4+8                     1+1+1+2+3                  = 8
>  1;3;6;10
>  19 = 1+4+6+8                       1+2+2+3                    = 8
>  1;5;11
>  20 = 1+2+4+5+8                     1+1+2+1+3                  = 8
>  1;3;7;12
>  21 = 1+2+4+6+8                     1+1+2+2+3                  = 9
>  1;3;7;13
>  22 = 1+3+4+6+8                     1+1+2+2+3                  = 9
>  1;4;8;14
>  23 = 1+2+3+4+5+8                   1+1+1+2+1+3                = 9
>  1;3;6;10
>