

A193494


Worst case of an unbalanced recursive algorithm over all nnode binary trees.


1



0, 1, 2, 4, 5, 7, 9, 13, 14, 16, 18, 22, 24, 28, 32, 40, 41, 43, 45, 49, 51, 55, 59, 67, 69, 73, 77, 85, 89, 97, 105, 121, 122, 124, 126, 130, 132, 136, 140, 148, 150, 154, 158, 166, 170, 178, 186, 202, 204, 208, 212, 220, 224, 232, 240, 256, 260
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


COMMENTS

Solves the recurrence a(0) = 0, a(n+1) = 1 + max_{0 <= k <= nk}(2a(k) + a(nk)).
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
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^{lg 3});
a(n) = 2^{nu(n)1} + a(n1) when n>0 and has nu(n) 1bits in binary;
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^(t1)*3^{e_t} + 2^t1)/2;
The generating function has the form (t_0 + t_0*t_1 + t_0*t_1*t_2 + ...)/ (1z), where t_0 = z and t_k = z^{2^{k1}} + 2*z^{2^k} for k > 0.


MAPLE

a:= proc(n) option remember;
`if`(n=0, 0, 1 +max(seq(2*a(k)+a(n1k), k=0..(n1)/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[n1k], {k, 0, (n1)/2}]]


PROG

(PARI) a=vector(60); a[1]=0; for(n=0, #a2, a[n+2]=1+vecmax(vector(n\2+1, k, 2*a[k]+a[nk+2]))); a \\ Charles R Greathouse IV, Jul 29 2011


CROSSREFS

lg(a[n]a[n1]) is A000120[n]1, for n>0.
Sequence in context: A288511 A249058 A105771 * A161832 A078404 A056908
Adjacent sequences: A193491 A193492 A193493 * A193495 A193496 A193497


KEYWORD

nonn


AUTHOR

Don Knuth, Jul 28 2011


EXTENSIONS

Third formula corrected by Don Knuth, Dec 08 2011


STATUS

approved



