

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



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*(k1) <= n) and (j <= nj*(k1)) then
t0:=t0+binomial(nj*(k1), j)*(1)^(j+1)/2^((k+1)*j);
fi;
od;
od:
RETURN(4^n*t0);
end;


CROSSREFS



KEYWORD

nonn


AUTHOR



STATUS

approved



