login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A158618 Number of gates in Ladner-Fisher prefix circuit 1

%I

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 24 00:28 EDT 2021. Contains 346265 sequences. (Running on oeis4.)