login
Number of gates in Ladner-Fisher prefix circuit.
1

%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