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

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.

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 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.

References

• Guy, Richard K. (2004). Unsolved problems in number theory (3rd ed.). Springer-Verlag. pp. 169–171. ISBN 978-0-387-20860-2. 
• Kutz, Martin (2002). "Lower Bounds For Lucas Chains". SIAM J. Comput. 31 (6): 1896–1908. doi:10.1137/s0097539700379255. http://www.mpi-inf.mpg.de/~mkutz/pubs/Kutz_LucasChains.pdf. 
• Montgomery, Peter L. (1983). "Evaluating Recurrences of Form X_m+n = f(X_m, X_n, X_m-n) Via Lucas Chains" (PS). Unpublished. http://cr.yp.to/bib/1992/montgomery-lucas.ps.