%I #10 Jul 29 2022 21:55:21
%S 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,
%T 55,57,61,64,67,69,74,75,77,79,82,84,87,89,93,95,98,100,104,107,110,
%U 112,117,119,122,124,128,131,134,136,141,143,147,149,153
%N Number of gates in Ladner-Fisher prefix circuit.
%D D. E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 0. See exercise 7.1.2.36 and solution.
%D R. E. Ladner and M. J. Fischer, Parallel Prefix Computation, JACM 27 (1980) 831-838.
%H Andrew Howroyd, <a href="/A158618/b158618.txt">Table of n, a(n) for n = 1..1000</a>
%F With s = floor(n/2), r = ceiling(n/2) and a(1) = b(1) = 0,
%F recurrence relation is a(n) = s + b(r) + a(s), b(n) = 2s-1 + a(r).
%F If n = 2^m then a(n) = 4n+1 - Fibonacci(m+5).
%o (PARI)
%o b(n)={if(n<=1, 0, 2*(n\2) - 1 + a((n+1)\2))}
%o a(n)={if(n<=1, 0, n\2 + b((n+1)\2) + a(n\2))} \\ _Andrew Howroyd_, Mar 28 2020
%K nonn
%O 1,3
%A _Frank Ruskey_, Mar 22 2009
%E Terms a(41) and beyond from _Andrew Howroyd_, Mar 28 2020