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. 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. An introduction is given by Knuth.[1]

Examples

As an example: v = (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: so for example we only need 7 multiplications to calculate 5³¹:

5² = 5¹ × 5¹

5³ = 5² × 5¹

5⁶ = 5³ × 5³

5¹² = 5⁶ × 5⁶

5²⁴ = 5¹² × 5¹²

5³⁰ = 5²⁴ × 5⁶

5³¹ = 5³⁰ × 5¹

Methods for computing addition chains

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 to calculate relatively short chains exist. One very well known technique to calculate relatively short addition chains is the binary method, similar to exponentiation by squaring. Other well-known methods are the factor method and window method.[3]

Chain length

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

${\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 Hamming weight (the number of ones) of the binary expansion of n.

It is clear that l(2n) ≤ l(n)+1. Strict inequality is possible, as l(382) = l(191) = 11, observed by Knuth.[5]

The first integer with l(2n) < l(n) is n = 375494703,[6] which is followed by 602641031, 619418303, and so on (sequence A230528 in the OEIS).

Brauer chain

A Brauer chain or star addition chain is an addition chain in which one of the summands is always the previous chain: that is,

for each k>0: a_k = a_k-1 + a_j for some j < k.

A Brauer number is one for which the Brauer chain is minimal.[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.

Scholz conjecture

Main article: Scholz conjecture

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]

See also

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

References

1. D. E. Knuth, The Art of Computer Programming, Vol 2, "Seminumerical Algorithms", Section 4.6.3, 3rd edition, 1997
2. Downey, Peter; Leong, Benton; Sethi, Ravi (1981). "Computing sequences with addition chains". SIAM Journal on Computing. 10 (3): 638–646. doi:10.1137/0210047.. A number of other papers state that finding a shortest addition chain for a single number is NP-complete, citing this paper, but it does not claim or prove such a result.
3. Otto, Martin (2001), Brauer addition-subtraction chains (PDF), Diplomarbeit, University of Paderborn, archived from the original (PDF) on 2013-10-19, retrieved 2013-10-19.
4. A. Schönhage A lower bound on the length of addition chains, Theoret. Comput. Sci. 1 (1975), 1–12.
5. Guy (2004) p.169
6. Clift, Neill Michael (2011). "Calculating optimal addition chains" (PDF). Computing. 91 (3): 265–284. doi:10.1007/s00607-010-0118-8.
7. Achim Flammenkamp , Shortest Addition Chains

• 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.

External links

• 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"