View source for Addition chain

In [[mathematics]], an '''addition chain''' for computing a positive integer {{mvar|n}} can be given by a [[sequence]] of [[natural number]]s starting with 1 and ending with {{mvar|n}}, such that each number in the sequence is the sum of two previous numbers. 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.<ref>D. E. Knuth, ''[[The Art of Computer Programming]]'', Vol 2, "Seminumerical Algorithms", Section 4.6.3, 3rd edition, 1997</ref>

==Examples==
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 {{mvar|n}} using only seven multiplications, instead of the 30 multiplications that one would get from repeated multiplication, and eight multiplications with [[exponentiation by squaring]]:
:{{mvar|n}}<sup>2</sup> = {{mvar|n}} × {{mvar|n}}
:{{mvar|n}}<sup>3</sup> = {{mvar|n}}<sup>2</sup> × {{mvar|n}}
:{{mvar|n}}<sup>6</sup> = {{mvar|n}}<sup>3</sup> × {{mvar|n}}<sup>3</sup>
:{{mvar|n}}<sup>12</sup> = {{mvar|n}}<sup>6</sup> × {{mvar|n}}<sup>6</sup>
:{{mvar|n}}<sup>24</sup> = {{mvar|n}}<sup>12</sup> × {{mvar|n}}<sup>12</sup>
:{{mvar|n}}<sup>30</sup> = {{mvar|n}}<sup>24</sup> × {{mvar|n}}<sup>6</sup>
:{{mvar|n}}<sup>31</sup> = {{mvar|n}}<sup>30</sup> × {{mvar|n}}

==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.<ref>{{citation|first1=Peter|last1=Downey|first2=Benton|last2=Leong|first3=Ravi|last3=Sethi|title=Computing sequences with addition chains|journal=[[SIAM Journal on Computing]]|volume=10|issue=3|year=1981|pages=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.</ref> 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.<ref name=otto>{{citation|url=http://math-www.uni-paderborn.de/~aggathen/Publications/ott01.pdf|series=Diplomarbeit|title=Brauer addition-subtraction chains|last=Otto|first=Martin|year=2001|publisher=University of Paderborn|access-date=2013-10-19|archive-url=https://web.archive.org/web/20131019165828/http://math-www.uni-paderborn.de/~aggathen/Publications/ott01.pdf|archive-date=2013-10-19|url-status=dead}}.</ref>

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 <math>n</math> is obtained recursively, from an addition chain for <math>n'=\lfloor n/2\rfloor</math>. If <math>n</math> is even, it can be obtained in a single additional sum, as <math>n=n'+n'</math>. If <math>n</math> is odd, this method uses two sums to obtain it, by computing <math>n-1=n'+n'</math> and then adding one.<ref name=otto/>

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

==Chain length==
Let <math>l(n)</math> denote the smallest <math>s</math> so that there exists an addition chain
of length <math>s</math> which computes <math>n</math>.
It is known that
<math display=block>\log_2 n+ \log_2 \nu(n)-2.13\leq l(n) \leq \log_2 n+ \nu(n)-1,</math>
<math display=block>l(n) \leq \log_2 n + \bigl(1+o(1)\bigr)\frac{\log_2 n}{\log_2 \log_2 n},</math>
where <math>\nu(n)</math> is the [[Hamming weight]] (the number of ones) of the binary expansion of <math>n</math>.<ref>{{citation|last=Schönhage|first=Arnold|authorlink=Arnold Schönhage|doi=10.1016/0304-3975(75)90008-0|issue=1|journal=[[Theoretical Computer Science (journal)|Theoretical Computer Science]]|pages=1–12|title=A Lower Bound for the Length of Addition Chains|volume=1|year=1975|doi-access=}}</ref>

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

==Brauer chain==
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.<ref name=G169/>

Brauer proved that
:{{math|''l''<sup>*</sup>(2<sup>''n''</sup>−1) ≤ ''n'' − 1 + ''l''<sup>*</sup>(''n'')}}
where {{tmath|l^*}} is the length of the shortest star chain.<ref>{{cite journal | last1=Brauer | first1=Alfred | title=On addition chains | doi=10.1090/S0002-9904-1939-07068-7  | mr=0000245  | year=1939 | journal=[[Bulletin of the American Mathematical Society]] | issn=0002-9904 | volume=45 | issue=10 | pages=736–739| doi-access=free }}</ref>  For many values of <math>n</math>, and in particular for <math>n<12509</math>, they are equal:<ref>Achim Flammenkamp, [http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html Shortest Addition Chains]</ref> {{math|1=''l''(''n'')&nbsp;=&nbsp;''l''<sup>*</sup>(''n'')}}. But Hansen showed that there are some values of ''n'' for which {{math|''l''(''n'')&nbsp;≠&nbsp;''l''<sup>*</sup>(''n'')}}, such as {{math|1=''n''&nbsp;=&nbsp;2<sup>6106</sup>&nbsp;+&nbsp;2<sup>3048</sup>&nbsp;+&nbsp;2<sup>2032</sup>&nbsp;+&nbsp;2<sup>2016</sup>&nbsp;+&nbsp;1}} which has {{math|1=''l''<sup>*</sup>(''n'')&nbsp;=&nbsp;6110, ''l''(''n'')&nbsp;≤&nbsp;6109}}. The smallest such ''n'' is 12509.

==Scholz conjecture==
{{main|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
:<math> l(2^n-1) \le n - 1 + l(n). </math>

This inequality is known to hold for all Hansen numbers, a generalization of Brauer numbers; Neill Clift checked by computer that all <math> n \le 5784688 </math> are Hansen (while 5784689 is not).<ref name=Clift>{{cite journal |first=Neill Michael |last=Clift |year=2011 |title=Calculating optimal addition chains |journal=Computing |volume=91 |issue=3 |pages=265–284 |doi=10.1007/s00607-010-0118-8 |url=https://link.springer.com/content/pdf/10.1007%2Fs00607-010-0118-8.pdf|doi-access=free }}</ref>  Clift further verified that in fact <math> l(2^n-1) = n - 1 + l(n)</math> for all <math>n \le 64</math>.<ref name=G169>{{cite book|author=Richard K. Guy|authorlink=Richard K. Guy|title=Unsolved Problems in Number Theory|publisher=[[Springer-Verlag]]|year=2004|isbn=978-0-387-20860-2|oclc=54611248 | zbl=1058.11001}}  Section C6, p.169.</ref>

==See also==
* [[Addition-subtraction chain]]
* [[Vectorial addition chain]]
* [[Lucas chain]]

==References==
{{reflist}}

==External links==
* {{OEIS el|sequencenumber=A003313|name=Length of shortest addition chain for n}}. Note that the initial "1" is not counted (so element #1 in the sequence is 0).
*[http://www.numdam.org/item?id=JTNB_1994__6_1_21_0 F. Bergeron, J. Berstel. S. Brlek "Efficient computation of addition chains"]

{{DEFAULTSORT:Addition Chain}}
[[Category:Addition chains|*]]
[[Category:NP-complete problems]]