|
| |
|
|
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
|
| |
|
|
