OFFSET
0,3
COMMENTS
Solves the recurrence a(0) = 0, a(n+1) = 1 + Max_{0 <= k <= n-k} (2*a(k) + a(n-k)).
a(floor(n/2)) is also the number of white areas in the elementary cellular automata based on rule 126 completed up to generation n. - Philippe Beaudoin, Feb 03 2014
REFERENCES
(I think I've seen it years ago, but I have no idea where.)
LINKS
Charles R Greathouse IV, Table of n, a(n) for n = 0..10000
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 30.
Don Knuth: I may refer to this sequence in my "Christmas tree lecture" this year (2011).
Eric Weisstein's World of Mathematics, Rule 126.
FORMULA
a(n) = O(n^(log_2(3)));
a(n) = 2^(nu(n)-1) + a(n-1) when n>0 and has nu(n) 1-bits in binary (A000120);
If n = 2^(e_1) + ... + 2^(e_t) with e_1 > ... > e_t >= 0, then a(n) = ((3^(e_1) + 2*3^(e_2) + ... + 2^(t-1)*3^(e_t) + 2^t-1)/2;
The generating function has the form (t_0 + t_0*t_1 + t_0*t_1*t_2 + ...)/ (1-z), where t_0 = z and t_k = z^{2^{k-1}} + 2*z^{2^k} for k > 0.
a(n) = (A006046(n+1) - 1) / 2. - Kevin Ryde, Jan 30 2022
MAPLE
a:= proc(n) option remember;
`if`(n=0, 0, 1 +max(seq(2*a(k)+a(n-1-k), k=0..(n-1)/2)))
end:
seq(a(n), n=0..60); # Alois P. Heinz, Jul 29 2011
MATHEMATICA
a[0]=0; a[n_]:=a[n]=1+Max[Table[2a[k]+a[n-1-k], {k, 0, (n-1)/2}]]
PROG
(PARI) a=vector(60); a[1]=0; for(n=0, #a-2, a[n+2]=1+vecmax(vector(n\2+1, k, 2*a[k]+a[n-k+2]))); a \\ Charles R Greathouse IV, Jul 29 2011
CROSSREFS
KEYWORD
nonn
AUTHOR
Don Knuth, Jul 28 2011
EXTENSIONS
Third formula corrected by Don Knuth, Dec 08 2011
STATUS
approved