In mathematics, an addition chain for computing a positive integer n can be given by a sequence of natural numbers v and a sequence of index pairs w such that each term in v is the sum of two previous terms, the indices of those terms being specified by w:
- v =(v0,...,vs), with v0 = 1 and vs = n
- for each 0< i ≤ s holds: vi = vj + vk, with wi=(j,k) and 0 ≤ j,k ≤ i − 1
Often only v is given since it is easy to extract w from v, but sometimes w is not uniquely reconstructible. An introduction is given by Knuth.
Read more about Addition Chain: Examples, Methods For Computing Addition Chains, Chain Length, Brauer Chain, Scholz Conjecture
Famous quotes containing the words addition and/or chain:
“The most important American addition to the World Experience was the simple surprising fact of America. We have helped prepare mankind for all its later surprises.”
—Daniel J. Boorstin (b. 1914)
“It could not have come down to us so far,
Through the interstices of things ajar
On the long bead chain of repeated birth,
To be a bird while we are men on earth,”
—Robert Frost (1874–1963)