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!)
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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 22 19:03 EDT 2020. Contains 337953 sequences. (Running on oeis4.)