|
Search: id:A158618
|
|
|
| A158618 |
|
Number of gates in Ladner-Fisher prefix circuit |
|
+0
1
|
|
| 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; listen)
|
|
|
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 this_sequence A000788 A053039 A027861
Adjacent sequences: A158615 A158616 A158617 this_sequence A158619 A158620 A158621
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Frank Ruskey (ruskey(AT)cs.uvic.ca), Mar 22 2009
|
|
|
Search completed in 0.002 seconds
|
