login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A193494 Worst case of an unbalanced recursive algorithm over all n-node 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 <= n-k}(2a(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

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(n-1) when n>0 and has nu(n) 1-bits 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^(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.

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

lg(a[n]-a[n-1]) 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 15 17:55 EDT 2018. Contains 316237 sequences. (Running on oeis4.)