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 =(v₀,...,v_s), with v₀ = 1 and v_s = n

for each 0< i ≤ s holds: v_i = v_j + v_k, with w_i=(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.