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

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.