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)
“To avoid tripping on the chain of the past, you have to pick it up and wind it about you.”
—Mason Cooley (b. 1927)