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₀, a₁, a₂, a₃, ...

that satisfies

a₀=1,

and

for each k > 0: a_k = a_i + a_j, and either a_i = a_j or |a_i − a_j| = a_m, for some i, j, m < k.<ref name=G169>Guy (2004) p.169</ref><ref>{{#invoke:citation/CS1|citation

|CitationClass=web }}</ref>

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.<ref>Kutz (2002)</ref> 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.<ref name=G169/>

References

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