An [addition chain](https://en.wikipedia.org/wiki/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](http://oeis.org/A003313) 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$)?**



Upper bound on length of addition chain
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[2] + Log[Log[n]] - 2 Log[Log[Log[n]]])/Log[2]] + (
 2^Floor[(c Log[2] + Log[Log[n]] - 2 Log[Log[Log[n]]])/Log[2]] 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).


