login
The OEIS is supported by the many generous donors to the OEIS 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

%I #16 Mar 06 2016 18:58:58

%S 0,1,9,57,307,1517,7103,32117,141711,614429,2629495,11141893,46846671,

%T 195760429,813970695,3370693013,13910890431,57246635581,235011903671,

%U 962772769829,3937069121647,16074491903309,65538899349479,266887332403125,1085630844057375,4411756408116573,17912600251244567,72670852531322949,294610539143446735

%N 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).

%C There are 2^{2n} choices for (u,v).

%C 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.

%C The longest carry propagation is n, for instance if u = 111...11, v = 000...01. See A050602 for further examples.

%H N. J. A. Sloane, <a href="/A192054/b192054.txt">Table of n, a(n) for n = 0..250</a>

%H Nicholas Pippenger, <a href="http://dx.doi.org/10.1006/jagm.2002.1216">Analysis of carry propagation in addition: an elementary approach</a>, J. Algorithms 42 (2002), 317-333.

%F Pippenger's formula is given in the Maple code.

%p C:=proc(n) local t0,j,k;

%p t0:=0;

%p for k from 1 to n+1 do

%p for j from 1 to floor(n/k) do

%p if (j*(k-1) <= n) and (j <= n-j*(k-1)) then

%p t0:=t0+binomial(n-j*(k-1),j)*(-1)^(j+1)/2^((k+1)*j);

%p fi;

%p od;

%p od:

%p RETURN(4^n*t0);

%p end;

%K nonn

%O 0,3

%A _N. J. A. Sloane_, Jun 21 2011

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 23 11:40 EST 2024. Contains 370283 sequences. (Running on oeis4.)