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:
“But the best read naturalist who lends an entire and devout attention to truth, will see that there remains much to learn of his relation to the world, and that it is not to be learned by any addition or subtraction or other comparison of known quantities, but is arrived at by untaught sallies of the spirit, by a continual self-recovery, and by entire humility.”
—Ralph Waldo Emerson (1803–1882)
“Loyalty to petrified opinions never yet broke a chain or freed a human soul in this world—and never will.”
—Mark Twain [Samuel Langhorne Clemens] (1835–1910)