On the distribution of the minimal length of addition chains
A sequence of integers $1=a_0 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\in [2^m, 2^{m+1})$, we show that there exist positive constants $K_3$ and $K_4$ such that $$ K_3^r \left(\frac{m^2}{r}\right)^r\le G\left(m,r\right)\le K_4^r \left(\frac{m^2}{r} \right)^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.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.28374
curl -X POST /api/v1/records/arxiv/2609.28374/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.28374/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'