A190868 Let C(n) be the expected length of the longest carry chain when two n-bit binary numbers are added; sequence gives a(n) = 2^(2n-1)*C(n).

0, 14, 106, 598, 3002, 14142, 64106, 283166, 1228346, 5257966, 22281738, 93689246, 391512666, 1627925006, 6741353258, 27821715326, 114493140090, 470023545198, 1925545015370, 7874137194718, 32148981709466, 131077794504654, 533774656417642, 2171261671337534, 8823512782678714, 35825200435380270

Offset

2,2

Comments

The addition is carried out by a parallel adder as described by J. von Neumann.

Links

Table of n, a(n) for n=2..27.

Volker Claus, Die mittlere Additionsdauer eines Paralleladdierwerks, Acta Informat. 2 (1973), 283-291.

D. E. Knuth, The average time for carry propagation, Nederl. Akad. Wetensch. Indag. Math., 81 (2) (1978), 238-242.

Nicholas Pippenger, Analysis of carry propagation in addition: an elementary approach, J. Algorithms 42 (2002), 317-333.

Formula

C(n) = E(n)-1, where E(n) is defined in A190866.

Example

C(n) for n >= 2: 0, 7/16, 53/64, 299/256, 1501/1024, 7071/4096, 32053/16384, 141583/65536, ...

Maple

See A190866.

Crossrefs

Cf. A190866.

Sequence in context: A285752 A076128 A206761 * A125351 A126509 A200056

Adjacent sequences: A190865 A190866 A190867 * A190869 A190870 A190871

Keyword

nonn,frac

Author

R. J. Mathar and N. J. A. Sloane, May 22 2011

Status

approved