As an example: (1,2,3,6,12,24,30,31) is an addition chain for 31 of length 7, since

2 = 1 + 1

3 = 2 + 1

6 = 3 + 3

12 = 6 + 6

24 = 12 + 12

30 = 24 + 6

31 = 30 + 1

Addition chains can be used for addition-chain exponentiation. This method allows exponentiation with integer exponents to be performed using a number of multiplications equal to the length of an addition chain for the exponent. For instance, the addition chain for 31 leads to a method for computing the 31st power of any number n using only seven multiplications, instead of the 30 multiplications that one would get from repeated multiplication, and eight multiplications with exponentiation by squaring:

n² = n × n

n³ = n² × n

n⁶ = n³ × n³

n¹² = n⁶ × n⁶

n²⁴ = n¹² × n¹²

n³⁰ = n²⁴ × n⁶

n³¹ = n³⁰ × n

Calculating an addition chain of minimal length is not easy; a generalized version of the problem, in which one must find a chain that simultaneously forms each of a sequence of values, is NP-complete.^[2] There is no known algorithm which can calculate a minimal addition chain for a given number with any guarantees of reasonable timing or small memory usage. However, several techniques are known to calculate relatively short chains that are not always optimal.^[3]

One very well known technique to calculate relatively short addition chains is the binary method, similar to exponentiation by squaring. In this method, an addition chain for the number ${\displaystyle n}$  is obtained recursively, from an addition chain for ${\displaystyle n'=\lfloor n/2\rfloor }$ . If ${\displaystyle n}$  is even, it can be obtained in a single additional sum, as ${\displaystyle n=n'+n'}$ . If ${\displaystyle n}$  is odd, this method uses two sums to obtain it, by computing ${\displaystyle n-1=n'+n'}$  and then adding one.^[3]

The factor method for finding addition chains is based on the prime factorization of the number ${\displaystyle n}$  to be represented. If ${\displaystyle n}$  has a number ${\displaystyle p}$  as one of its prime factors, then an addition chain for ${\displaystyle n}$  can be obtained by starting with a chain for ${\displaystyle n/p}$ , and then concatenating onto it a chain for ${\displaystyle p}$ , modified by multiplying each of its numbers by ${\displaystyle n/p}$ . The ideas of the factor method and binary method can be combined into Brauer's m-ary method by choosing any number ${\displaystyle m}$  (regardless of whether it divides ${\displaystyle n}$ ), recursively constructing a chain for ${\displaystyle \lfloor n/m\rfloor }$ , concatenating a chain for ${\displaystyle m}$  (modified in the same way as above) to obtain ${\displaystyle m\lfloor n/m\rfloor }$ , and then adding the remainder. Additional refinements of these ideas lead to a family of methods called sliding window methods.^[3]

Let ${\displaystyle l(n)}$  denote the smallest ${\displaystyle s}$  so that there exists an addition chain of length ${\displaystyle s}$  which computes ${\displaystyle n}$ . It is known that

${\displaystyle \log _{2}(n)+\log _{2}(\nu (n))-2.13\leq l(n)\leq \log _{2}(n)+\log _{2}(n)(1+o(1))/\log _{2}(\log _{2}(n))}$ ,

where ${\displaystyle \nu (n)}$  is the Hamming weight (the number of ones) of the binary expansion of ${\displaystyle n}$ .^[4]

One can obtain an addition chain for ${\displaystyle 2n}$  from an addition chain for ${\displaystyle n}$  by including one additional sum ${\displaystyle 2n=n+n}$ , from which follows the inequality ${\displaystyle l(2n)\leq l(n)+1}$  on the lengths of the chains for ${\displaystyle n}$  and ${\displaystyle 2n}$ . However, this is not always an equality, as in some cases ${\displaystyle 2n}$  may have a shorter chain than the one obtained in this way. For instance, ${\displaystyle l(382)=l(191)=11}$ , observed by Knuth.^[5] It is even possible for ${\displaystyle 2n}$  to have a shorter chain than ${\displaystyle n}$ , so that ${\displaystyle l(2n)<l(n)}$ ; the smallest ${\displaystyle n}$  for which this happens is ${\displaystyle n=375494703}$ ,^[6] which is followed by ${\displaystyle 602641031}$ , ${\displaystyle 619418303}$ , and so on (sequence A230528 in the OEIS).

A Brauer chain or star addition chain is an addition chain in which each of the sums used to calculate its numbers uses the immediately previous number. A Brauer number is a number for which a Brauer chain is optimal.^[5]

Brauer proved that

l^*(2ⁿ−1) ≤ n − 1 + l^*(n)

where ${\displaystyle l^{*}}$  is the length of the shortest star chain. For many values of n, and in particular for n < 12509, they are equal:^[7] l(n) = l^*(n). But Hansen showed that there are some values of n for which l(n) ≠ l^*(n), such as n = 2⁶¹⁰⁶ + 2³⁰⁴⁸ + 2²⁰³² + 2²⁰¹⁶ + 1 which has l^*(n) = 6110, l(n) ≤ 6109. The smallest such n is 12509.

The Scholz conjecture (sometimes called the Scholz–Brauer or Brauer–Scholz conjecture), named after Arnold Scholz and Alfred T. Brauer), is a conjecture from 1937 stating that

${\displaystyle l(2^{n}-1)\leq n-1+l(n).}$ 

This inequality is known to hold for all Hansen numbers, a generalization of Brauer numbers; Neill Clift checked by computer that all ${\displaystyle n\leq 5784688}$  are Hansen (while 5784689 is not).^[6] Clift further verified that in fact ${\displaystyle l(2^{n}-1)=n-1+l(n)}$  for all ${\displaystyle n\leq 64}$ .^[5]

• Addition-subtraction chain
• Vectorial addition chain
• Lucas chain

• Brauer, Alfred (1939). "On addition chains". Bulletin of the American Mathematical Society. 45 (10): 736–739. doi:10.1090/S0002-9904-1939-07068-7. ISSN 0002-9904. MR 0000245.
• Richard K. Guy (2004). Unsolved Problems in Number Theory. Springer-Verlag. ISBN 978-0-387-20860-2. OCLC 54611248. Zbl 1058.11001. Section C6.

• http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html
• OEIS sequence A003313 (Length of shortest addition chain for n). Note that the initial "1" is not counted (so element #1 in the sequence is 0).
• F. Bergeron, J. Berstel. S. Brlek "Efficient computation of addition chains"