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

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
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

On the minimal length of addition chains

Jean–Marie De Koninck, William Verreault, Nicolas Doyon
Functiones et Approximatio Commentarii Mathematici
Geometric and Algebraic Topology
article

On the minimal length of addition chains

Jean–Marie De Koninck, William Verreault, Nicolas Doyon
article en

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):=\#\{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}.$$

Functiones et Approximatio Commentarii MathematiciVol. 74(1)
Openalex Percentile: Top 81%
Geometric and Algebraic Topology
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.