Lucas chain

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

$a_0,a_1,a_2,a_3,\dots$

that satisfies Template:Math, and, for each Template:Math,

$a_k=a_i+a_j,$

and either

$a_i=a_j\text{ or }|a_i-a_j|=a_m$

for some Template:Math.

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. If Template:Math is the length of the shortest Lucas chain for Template:Mvar, then Kutz has shown that most Template:Mvar do not have Template:Math, where φ is the Golden ratio.

References

• Template:Cite book
• Template:Cite journal
• Template:Cite journal