The OEIS is supported by the many generous donors to the OEIS Foundation. Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 60th year, we have over 367,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”). Other ways to Give
 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A192054 Let u, v be binary vectors of length n, let f(u,v) be length of longest carry propagation when we form the binary sum u+v; then a(n) = Sum_{u,v} f(u,v). 2
 0, 1, 9, 57, 307, 1517, 7103, 32117, 141711, 614429, 2629495, 11141893, 46846671, 195760429, 813970695, 3370693013, 13910890431, 57246635581, 235011903671, 962772769829, 3937069121647, 16074491903309, 65538899349479, 266887332403125, 1085630844057375, 4411756408116573, 17912600251244567, 72670852531322949, 294610539143446735 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,3 COMMENTS There are 2^{2n} choices for (u,v). A carry propagation is started if u_i = v_i = 1, and is extended if one bit of either u or v is 0 and the other is 1. The longest carry propagation is n, for instance if u = 111...11, v = 000...01. See A050602 for further examples. LINKS N. J. A. Sloane, Table of n, a(n) for n = 0..250 Nicholas Pippenger, Analysis of carry propagation in addition: an elementary approach, J. Algorithms 42 (2002), 317-333. FORMULA Pippenger's formula is given in the Maple code. MAPLE C:=proc(n) local t0, j, k; t0:=0; for k from 1 to n+1 do for j from 1 to floor(n/k) do if (j*(k-1) <= n) and (j <= n-j*(k-1)) then t0:=t0+binomial(n-j*(k-1), j)*(-1)^(j+1)/2^((k+1)*j); fi; od; od: RETURN(4^n*t0); end; CROSSREFS Sequence in context: A338080 A064838 A027210 * A045720 A014916 A045635 Adjacent sequences: A192051 A192052 A192053 * A192055 A192056 A192057 KEYWORD nonn AUTHOR N. J. A. Sloane, Jun 21 2011 STATUS approved

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

Last modified December 8 08:36 EST 2023. Contains 367663 sequences. (Running on oeis4.)