%I A158618
%S A158618 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,
%T A158618 57,61,64,67,69,74,75,77,79,82,84,87,89,93
%N A158618 Number of gates in Ladner-Fisher prefix circuit
%D A158618 D.E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 0. See 
               exercise 7.1.2.36 and solution.
%D A158618 R.E. Ladner and M.J. Fischer, Parallel Prefix Computation, JACM 27 (1980) 
               831-838.
%F A158618 With s = floor(n/2), r = ceiling(n/2) and a(1) = b(1) = 0,
%F A158618 recurrence relation is a(n) = s + b(r) + a(s), b(n) = 2s-1 + a(r).
%F A158618 If n = 2^m then a(n) = 4n+1 - Fibonacci(m+5).
%Y A158618 Sequence in context: A140205 A140206 A007818 this_sequence A000788 A053039 
               A027861
%Y A158618 Adjacent sequences: A158615 A158616 A158617 this_sequence A158619 A158620 
               A158621
%K A158618 nonn
%O A158618 1,3
%A A158618 Frank Ruskey (ruskey(AT)cs.uvic.ca), Mar 22 2009