Lucas chain

In mathematics, a Lucas chain is a restricted type of addition chain, named for the French mathematician Édouard Lucas. It is a sequence

${\displaystyle a_{0},a_{1},a_{2},a_{3},\ldots }$

that satisfies a₀=1, and, for each k > 0,

${\displaystyle a_{k}=a_{i}+a_{j},}$

and either

${\displaystyle a_{i}=a_{j}{\text{ or }}\vert a_{i}-a_{j}\vert =a_{m}}$

for some i, j, m < k.^[1][2]

The sequence of powers of 2 (1, 2, 4, 8, 16, ...) and the Fibonacci sequence (with a slight adjustment of the starting point 1, 2, 3, 5, 8, ...) are simple examples of Lucas chains.

Lucas chains were introduced by Peter Montgomery in 1983.^[3] If L(n) is the length of the shortest Lucas chain for n, then Kutz has shown that most n do not have L < (1-ε) log_φ(n), where φ is the Golden ratio.^[1]