On the minimal length of addition chains

2025/04/09 by De Koninck, Jean-Marie, Doyon, Nicolas, Verreault, William
#11B83 (Primary) 11Y55 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT)

paper · doi:10.48550/arxiv.2504.07332

Abstract

We denote by ℓ(n) the minimal length of an addition chain leading to n and we define the counting function F(m,r):=#\n∈[2^m, 2^m+1):ℓ(n)≤ m+r\, where m is a positive integer and r≥ 0 is a real number. We show that for 0< c<log 2 and for any ε>0, we have as m→ ∞, F(m,(cm)/(log m))lt;exp(cm+(ε mloglog m)/(log m)) and F(m,(cm)/(log m))gt;exp(cm-((1+ε)cmloglog m)/(log m)). This extends a result of Erdős which says that for almost all n, as n→∞, ℓ(n)=(log n)/(log 2)+(1+o(1))(log n)/(log log n).

Related

• The Scholz conjecture for n=2^m(23)+7, m ∈ ℕ^*
• Calculating optimal addition chains
• Computing Sequences with Addition Chains
• On addition chains and progress on the Scholz conjecture
• The Scholz conjecture on addition chain is true for infinitely many integers with ℓ(2n)= ℓ(n)