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.^[1]

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.^[2] 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]

References

1. Guy (2004) p.169
2. Kutz (2002)

• Guy, Richard K. (2004). Unsolved problems in number theory (3rd ed.). Springer-Verlag. pp. 169–171. ISBN 978-0-387-20860-2. Zbl 1058.11001.
• Kutz, Martin (2002). "Lower Bounds For Lucas Chains" (PDF). SIAM J. Comput. 31 (6): 1896–1908. doi:10.1137/s0097539700379255. Zbl 1055.11077.
• Montgomery, Peter L. (1983). "Evaluating Recurrences of Form X_m+n = f(X_m, X_n, X_m-n) Via Lucas Chains" (PS). Unpublished.