On the minimal length of addition chains
We denote by $\ell(n)$ the minimal length of an addition chain leading to $n$ and we define the counting function $$F(m,r):=\#\{n\in[2^m, 2^{m+1}):\ell(n)\le m+r\},$$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 $\varepsilon>0$, we have as $m\to \infty$,$$F\left(m,\frac{cm}{\log m}\right)<\exp\left(cm+\frac{\varepsilon m\log\log m}{\log m}\right)$$and$$F\left(m,\frac{cm}{\log m}\right)>\exp\left(cm-\frac{(1+\varepsilon)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}.$$
Authors
- Jean–Marie De Koninck (ORCID: https://orcid.org/0000-0003-4506-959X)
- William Verreault (ORCID: https://orcid.org/0009-0005-5433-596X)
- Nicolas Doyon
Publication Details
- Journal
- Functiones et Approximatio Commentarii Mathematici
- Published
- 2025-06-16
- DOI
- https://doi.org/10.7169/facm/241106-7-4
- Primary Topic
- Geometric and Algebraic Topology
- Type
- article
- Field-Weighted Citation Impact
- 0.00