**Addition chain**: 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 =, with v0 = 1 and vs = n
for each 0< i ≤ s holds: vi = vj + vk, with wi=(j,k) and 0 ≤ j,k ≤ i − 1Often only v is given since it is easy to extract w from v, but sometimes w is not uniquely reconstructible. The length of an addition chain is the number of sums needed to express all its numbers, which is one less than the cardinality of the sequence of numbers.