|
| |
|
|
A158618
|
|
Number of gates in Ladner-Fisher prefix circuit
|
|
0
| |
|
|
0, 1, 2, 4, 5, 7, 9, 12, 13, 15, 17, 20, 22, 25, 27, 31, 32, 34, 36, 39, 41, 44, 46, 50, 52, 55, 57, 61, 64, 67, 69, 74, 75, 77, 79, 82, 84, 87, 89, 93
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,3
|
|
|
REFERENCES
| D.E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 0. See exercise 7.1.2.36 and solution.
R.E. Ladner and M.J. Fischer, Parallel Prefix Computation, JACM 27 (1980) 831-838.
|
|
|
FORMULA
| With s = floor(n/2), r = ceiling(n/2) and a(1) = b(1) = 0,
recurrence relation is a(n) = s + b(r) + a(s), b(n) = 2s-1 + a(r).
If n = 2^m then a(n) = 4n+1 - Fibonacci(m+5).
|
|
|
CROSSREFS
| Sequence in context: A140205 A140206 A007818 * A000788 A053039 A027861
Adjacent sequences: A158615 A158616 A158617 * A158619 A158620 A158621
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Frank Ruskey (ruskey(AT)cs.uvic.ca), Mar 22 2009
|
| |
|
|
