TOPICS
Search

Addition Chain

An addition chain for a number n is a sequence 1=a_0<a_1<...<a_r=n, such that each member after a_0 is the sum of two earlier (not necessarily distinct) ones. The number r is called the length of the addition chain. For example,

1,1+1=2,2+2=4,4+2=6,6+2=8,8+6=14

is an addition chain for 14 of length r=5 (Guy 1994).

Let l(n) denote the minimum length of an addition chain for n, and let F(m,r) count the integers n in [2^m,2^(m+1)) for which l(n)<=m+r. De Koninck et al. (2026) proved that for every fixed 0<c<ln2, there are positive constants K_1 and K_2 such that

K_1^rm^r<=F(m,r)<=K_2^rm^r

for all sufficiently large m and all integers m^(0.9)<r<=cm/lnm. Their upper bound also holds for every integer r>m^(0.9).

See also

Brauer Chain, Hansen Chain, Scholz Conjecture

Explore with Wolfram|Alpha

WolframAlpha

More things to try:

References

De Koninck, J.-M.; Doyon, N.; and Verreault, W. "On the Distribution of the Minimal Length of Addition Chains." 23 Sep 2026. https://arxiv.org/abs/2609.28374.Guy, R. K. "Addition Chains. Brauer Chains. Hansen Chains." §C6 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 111-113, 1994.

Referenced on Wolfram|Alpha

Addition Chain

Cite this as:

Weisstein, Eric W. "Addition Chain." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/AdditionChain.html

Subject classifications