Lucas chain
From HandWiki
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
- ↑ 1.0 1.1 Guy (2004) p.169
- ↑ Weisstein, Eric W.. "Lucas Chain" (in en). https://mathworld.wolfram.com/LucasChain.html.
- ↑ Kutz (2002)
- 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 Xm+n = f(Xm, Xn, Xm-n) Via Lucas Chains" (PS). Unpublished. http://cr.yp.to/bib/1992/montgomery-lucas.ps.
![]() | Original source: https://en.wikipedia.org/wiki/Lucas chain.
Read more |