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 addition of a helpless, needy infant to a couple’s life limits freedom of movement, changes role expectancies, places physical demands on parents, and restricts spontaneity.”
—Jerrold Lee Shapiro (20th century)
“How have I been able to live so long outside Nature without identifying myself with it? Everything lives, moves, everything corresponds; the magnetic rays, emanating either from myself or from others, cross the limitless chain of created things unimpeded; it is a transparent network that covers the world, and its slender threads communicate themselves by degrees to the planets and stars. Captive now upon earth, I commune with the chorus of the stars who share in my joys and sorrows.”
—Gérard De Nerval (1808–1855)