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!)
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). 1
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 (list; graph; refs; listen; history; text; internal format)
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

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 March 1 03:32 EST 2021. Contains 341732 sequences. (Running on oeis4.)