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$)?
 A: 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).
A: 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
A: 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.
A: 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.
