Lucas chain explained

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] [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]

References

• Book: Guy, Richard K. . Richard K. Guy

. Richard K. Guy . Unsolved problems in number theory . . 3rd . 2004 . 978-0-387-20860-2 . 1058.11001 . 169–171 .

• Martin . Kutz . Lower Bounds For Lucas Chains . SIAM J. Comput. . 2002 . 31 . 6 . 1896–1908 . 1055.11077 . 10.1137/s0097539700379255.
• Peter L. . Montgomery . Peter Montgomery (mathematician) . Evaluating Recurrences of Form X_m+n = f(X_m, X_n, X_m-n) Via Lucas Chains . 1983 . Unpublished. PS .

Notes and References

1. Guy (2004) p.169
2. Web site: Weisstein. Eric W.. Lucas Chain. 2020-08-11. mathworld.wolfram.com. en.
3. Kutz (2002)