A190866 - OEIS

A190866

Let E(n) be the average number of steps required for the addition of two binary numbers of length n; sequence gives a(n) = 2^(2n-1)*E(n).

%I #27 May 30 2026 16:40:35

%S 1,8,46,234,1110,5050,22334,96874,414238,1752634,7355118,30670346,

%T 127243678,525730394,2164795918,8888836906,36411649918,148852878458,

%U 607462498670,2475300829258,10073160450270,40945074731674,166262166593486,674512144772970,2734211624758846,11075312596363962,44832399690121262,181370501947392138,733336266094313886,2963615247763178714

%N Let E(n) be the average number of steps required for the addition of two binary numbers of length n; sequence gives a(n) = 2^(2n-1)*E(n).

%C The addition is carried out by a parallel adder as described by J. von Neumann. Pippenger describes E(n) as the expected number of times that a "carry-save" adder must be used to clear all carries.

%H Volker Claus, <a href="https://doi.org/10.1007/BF00289501">Die mittlere Additionsdauer eines Paralleladdierwerks</a>, Acta Informat. 2 (1973), 283-291.

%H D. E. Knuth, <a href="https://doi.org/10.1016/1385-7258(78)90041-0">The average time for carry propagation</a>, Nederl. Akad. Wetensch. Indag. Math., 81 (2) (1978), 238-242.

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

%F The formulas used in the Maple program are due to Claus. Knuth gives an asymptotic expansion for E(n).

%e Values of E(n), n>=1: 1/2, 1, 23/16, 117/64, 555/256, 2525/1024, 11167/4096, 48437/16384, ...

%p q := proc(n,i)

%p option remember ;

%p if i > n then

%p 0 ;

%p elif i = 0 then

%p 1;

%p elif i = 1 then

%p if n >= 2 then

%p (procname(n-1,1)+1)/2 ;

%p else

%p 1/2 ;

%p end if;

%p elif i >=2 then

%p procname(n-1,i)+(1-procname(n-i+1,i))/2^i ;

%p end if;

%p end proc:

%p E := proc(n)

%p add( q(n,i),i=1..n) ;

%p end proc:

%p [seq(2^(2*n-1)*E(n),n=1..30)];

%t q[n_, i_] := q[n, i] = Which[i > n, 0, i == 0, 1, i == 1, If[n >= 2, (q[n-1, 1]+1)/2, 1/2], i >= 2, q[n-1, i] + (1-q[n-i+1, i])/2^i];

%t En[n_] := Sum[ q[n, i], {i, 1, n}];

%t Table[2^(2*n-1)*En[n], { n, 1, 30}] (* _Jean-François Alcover_, Aug 30 2024, after Maple program *)

%Y See A190868 for a closely related sequence.

%K nonn,frac

%O 1,2

%A _R. J. Mathar_ and _N. J. A. Sloane_, May 22 2011