Addition chain

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:

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"