info prev up next book cdrom email home

Addition Chain

An addition chain for a number $n$ is a Sequence $1=a_0<a_1<\ldots<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).

See also Brauer Chain, Hansen Chain, Scholz Conjecture


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.

© 1996-9 Eric W. Weisstein