On the distribution of the minimal length of addition chains
Abstract
A sequence of integers 1=a0<a1<⋯<ak=n is called an addition chain of length k if aj=as+at with 0≤ s,t<j for all integers j∈ {1,2,…,k}. We denote by ℓ(n) the minimal length of an addition chain leading to n. Here we investigate the distribution of the function ℓ through the counting function F(m,r):=#{n∈ [2m,2m+1):ℓ(n)≤ m+r} and show that, for every fixed 0<c<log 2, there exist positive constants K1 and K2 such that K1r mr≤ F(m,r)≤ K2r mr for all sufficiently large m and all integers m0.9<r≤ cm/log m. The upper bound also holds for every integer r>m0.9. Moreover, denoting by G(m,r) the number of \emph{distinct} addition chains of length m+r leading to an integer n∈ [2m, 2m+1), we show that there exist positive constants K3 and K4 such that K3r (m2/r)r≤ G(m,r)≤ K4r (m2/r )r provided m0.9<r<m. This improves and generalizes previous results on the minimal length of addition chains and addresses a question raised by Paul Erdős.
Related
BibTeX
@misc{koninck2026distribution,
title = {{On the distribution of the minimal length of addition chains}},
author = {Jean-Marie De Koninck and Nicolas Doyon and William Verreault},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.28374},
eprint = {2609.28374},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.28374},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - On the distribution of the minimal length of addition chains
AU - Jean-Marie De Koninck
AU - Nicolas Doyon
AU - William Verreault
PY - 2026
DA - 2026/09/23
PB - arXiv
DO - 10.48550/arxiv.2609.28374
UR - https://arxiv.org/abs/2609.28374
AB - A sequence of integers 1=a_0<a_1<⋯<a_k=n is called an addition chain of length k if a_j=a_s+a_t with 0≤ s,t<j for all integers j∈ {1,2,…,k}. We denote by ℓ(n) the minimal length of an addition chain leading to n. Here we investigate the distribution of the function ℓ through the counting function F(m,r):=#{n∈ [2^m,2^m+1):ℓ(n)≤ 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≤ F(m,r)≤ K_2^r m^r for all sufficiently large m and all integers m^0.9<r≤ cm/log m. The upper bound also holds for every integer r>m^0.9. Moreover, denoting by G(m,r) the number of \emph{distinct} addition chains of length m+r leading to an integer n∈ [2^m, 2^m+1), we show that there exist positive constants K_3 and K_4 such that K_3^r (m^2/r)^r≤ G(m,r)≤ K_4^r (m^2/r )^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ős.
ER -