Lucas chain
Appearance
In mathematics, a Lucas chain is a restricted type of addition chain, named for the French mathematician Édouard Lucas. It is a sequence
- a0, a1, a2, a3, ...
that satisfies
- a0=1,
and
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
[edit]- ^ a b Guy (2004) p.169
- ^ Weisstein, Eric W. "Lucas Chain". mathworld.wolfram.com. Retrieved 2020-08-11.
- ^ 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 Xm+n = f(Xm, Xn, Xm-n) Via Lucas Chains" (PS). Unpublished.