On the distribution of the minimal length of addition chains

A sequence of integers $1=a_0<a_1<\cdots <a_k=n$ is called an addition chain of length $k$ if $a_j=a_s+a_t$ with $0\le s,t<j$ for all integers $j\in \{1,2,\dots ,k\}$. We denote by $\ell (n)$ the minimal length of an addition chain leading to $n$. Here we investigate the distribution of the function $\ell$ through the counting function $F(m,r):=\#\{n\in [2^m,2^{m+1}):\ell (n)\le m+r\}$ and show that, for every fixed $0<c<\log 2$, there exist positive constants $K_1$ and $K_2$ such that $K_1^r{m}^r\le F(m,r)\le K_2^r{m}^r$ for all sufficiently large $m$ and all integers $m^{0.9}<r\le cm/\log m$. The upper bound also holds for every integer $r>m^{0.9}$. Moreover, denoting by $G(m,r)$ the number of distinct addition chains of length $m+r$ leading to an integer $n\in [2^m,2^{m+1})$, we show that there exist positive constants $K_3$ and $K_4$ such that $K_3^r{\left(\frac{m^2}{r}\right)}^r\le G\left(m,r\right)\le K_4^r{\left(\frac{m^2}{r}\right)}^r$ provided $m^{0.9}<r<m$. This improves and generalizes previous results on the minimal length of addition chains and addresses a question raised by Paul Erd\H{o}s.