# Upper bound on length of addition chain

An addition chain for $n$ is a finite sequence of integers starting at 1 and ending at $n$, such that each element is a sum of two previous elements. A short addition chain for $n$ can be used, for example, to calculate $x^n$ quickly by multiplying previously-calculated values.

Let $l(n)$ be the length of the shortest addition chain for $n$. I am looking for an upper bound on $l(n)$ of the form:

$$l(n) \leq C \cdot \log_2(n)$$

where $C$ is a constant.

The Wikipedia page cites the following bound from 1975: $$l(n) \leq \log_2(n) + \log_2(n)(1+o(1))/\log_2(\log_2(n)) < 2\log_2(n)$$

The OEIS page states several bounds, but without a clear reference: $$l(n) \leq (5/2) \log(n) = 1.73 \log_2(n)$$ $$l(n) \leq (4/3) \lfloor\log_2(n)\rfloor + 2$$

What is a reference for the best known upper bound of the form $l(n) \leq C \cdot \log_2(n)$ (the smallest value of $C$)?

## 4 Answers

Alfred Brauer, On addition chains, Bull. Amer. Math. Soc. 45 (1939), 736-739 http://www.ams.org/journals/bull/1939-45-10/S0002-9904-1939-07068-7/

gives inequalities of the type you mention: equation (11), ($\log n$ being the log with base e).

If $2^m < n<2^{m+1}$, then $$l(n) \leq \min_{1\leq r \leq m} \Bigl( (1+\frac{1}{r})\frac{\log n}{\log 2}+2^r-2 \Bigr) .$$ Choosing a good (but maybe not yet optimal value of $r=[\log \log n]+1$) he obtains for $n\geq 3$: $l(n)< \frac{\log n}{\log 2}\Bigl(1+\frac{1}{\log \log n}+\frac{2\log 2}{(\log n)^{1-\log 2}}\Bigr)$.

So, you get $l(n)< (1+\varepsilon)\frac{\log n}{\log 2}$, for any $\varepsilon>0$, valid if $n > n_{\varepsilon}$. This threshold $n_{\varepsilon}$ can be worked out from $\frac{1}{\log \log n}+\frac{2\log 2}{(\log n)^{1-\log 2}}\leq \varepsilon$.

If $n$ is large, then the expression $\frac{1}{\log \log n}$ will be the dominating one on the left hand side, and so $n_{\varepsilon}$ is about $\exp(\exp(1/\varepsilon))$.

As Brauer's result is stronger than the form $l(n)\leq C \log n$ you ask about there will not be much literature on this. In any case, $C$ may tend to $1$, but is close to $1$ only for quite large values of $n$.

Update: For a numerical value of $C$ proceed as follows: 1) The OEIS page links to the first 100.000 values of the sequence: http://oeis.org/A003313/b003313.txt Calculating for these values the corresponding value of $C$ shows that for n=71 the value $9/\log_2 n=1.46347$ is the maximal value. (Based on this data I would conjecture that this is for all $n$ the maximal value, I am not sure if there is more data available, maybe you have a fast algorithm to check it.)

In order to prove an upper bound: Brauer's calculation (see equation 11 in the reference given) does not choose the best value of $r$. Choosing $r=[ \frac{\log \log n}{\log 2} -2\frac{\log \log \log n}{\log 2}+c ]$ somewhat improves the estimate. (Here $c$ is a constant to be optimized below).

The expression $$\Bigl( (1+\frac{1}{r})\frac{\log n}{\log 2}+2^r-2 \Bigr)$$ then gives (ignoring the floor functon in the definition of $r$) $$1 - \frac{\log 4}{\log n} + \frac{2^c \log 2}{(\log \log n)^2} + \frac{\log 2}{ c \log 2 + \log \log n - 2 \log \log \log n}.$$ Then evaluating the function for various values $c$ and for a large value where one has numerical data, here with $n=100.000$, gives with $c=1.3$ a value of $C=1.61043$.

With the value of $r$ rounded to an integer, the expression is (in Mathematica Code) 1/Floor[(c Log + Log[Log[n]] - 2 Log[Log[Log[n]]])/Log] + ( 2^Floor[(c Log + Log[Log[n]] - 2 Log[Log[Log[n]]])/Log] Log[ 2] + Log[n/4])/Log[n]

With $c=2$ this gives a value of $C=1.620412$. In other words, if $n> 10^5$, the function $l(n)\leq 1.620412 \frac{\log n}{\log 2}$ by Brauer's bound, assuming one accepts (or formally proves) that for fixed $c$ and increasing $n$ the function above is decreasing. For smaller values one has the numerical data.

(Asymptotically, this value of $c$ is not the best possible value. If you have numerical data up to some other bound, you can optimize this $c$ again).

• So, $C$ can be made arbitrarily close to 1 for sufficiently large values of $n$? – Erel Segal-Halevi Sep 18 '15 at 8:47
• Should't the inequality be: $\frac{1}{\log \log n}+\frac{2\log 2}{(\log n)^{1-\log 2}}\leq \varepsilon$? – Erel Segal-Halevi Sep 18 '15 at 9:51
• (e.g, for $n=29$, the smallest length is 7 which is slightly above the bound). – Erel Segal-Halevi Sep 18 '15 at 10:20
• Yes, some minor correction just added. $C$ is close to 1, for quite large values of $n$. – Christian Elsholtz Sep 18 '15 at 13:43
• This leaves open the question: what is the smallest value of $C$ such that $l(n)\leq C\cdot \log_2(n)$ for every $n$ (or at least for $n\geq 3$)? – Erel Segal-Halevi Sep 19 '15 at 17:19

There is a new OEIS sequence A264803 in which Neill Clift's table of l(n), provided at A. Flammenkamp's web page, is used to determine the maximum values of l(n)/log2(n) in intervals 2^m < n < 2^(m+1) for m<=30

In this paper:

Wattel, E. & Jensen, G. "Efficient calculation of powers in a semigroup" Stichting Mathematisch Centrum. Zuivere Wiskunde, 1968, 1-18

they prove that $l(n)/log_2(n)\le1.463$ and takes on this value for $n=71$. This paper is interesting since it's an earlier usage of the Thurber sliding window method than the Thurber paper. The only reason I know about this paper is that it was referenced by a student doing a term paper and he was given the paper by one of the authors. I don't understand the interest in a bound like this mind you.

Subbarao, M. "Addition chains-some results and problems." Number theory and applications (1989): 555-574.

A slightly outdated reference, but seems like the best available for the problem.