On the minimal length of addition chains

Abstract

We denote by $\ell (n)$ the minimal length of an addition chain leading to $n$ and we define the counting function $$F(m,r):=\#\left\{n\in [2^m,2^{m+1}):\ell (n)\le m+r\right\},$$ where $m$ is a positive integer and $r\ge 0$ is a real number. We show that for $0<c<\log 2$ and for any $\epsilon >0$, we have as $m\to \infty$, $$F\left(m,\frac{cm}{\log m}\right)<\exp \left(cm+\frac{\epsilon m\log \log m}{\log m}\right)$$ and $$F\left(m,\frac{cm}{\log m}\right)>\exp \left(cm-\frac{(1+\epsilon )cm\log \log m}{\log m}\right).$$ This extends a result of Erdős which says that for almost all $n$, as $n\to \infty$, $$\ell (n)=\frac{\log n}{\log 2}+\left(1+o(1)\right)\frac{\log n}{\log \log n}.$$

arXiv comment24 pages