[seqfan] Re: A simple looking sequence is spontaneously breaking its monotony
M. F. Hasler
oeis at hasler.fr
Thu Oct 28 04:20:44 CEST 2021
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
>
More information about the SeqFan
mailing list