{{Short description|Restricted type of addition chain}} In mathematics, a '''Lucas chain''' is a restricted type of addition chain, named for the French mathematician Édouard Lucas. It is a sequence :<math>a_0, a_1, a_2, a_3, \ldots</math> that satisfies {{math|1=''a''<sub>0</sub>=1}}, and, for each {{math|''k'' > 0}}, : <math>a_k = a_i + a_j,</math> and either : <math>a_i = a_j \text{ or } \vert a_i - a_j \vert = a_m </math> for some {{math|1=''i'', ''j'', ''m'' < ''k''}}.<ref name="G169">Guy (2004) p.169</ref><ref>{{Cite web|last=Weisstein|first=Eric W.|title=Lucas Chain|url=https://mathworld.wolfram.com/LucasChain.html|access-date=2020-08-11|website=mathworld.wolfram.com|language=en}}</ref>
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.<ref>Kutz (2002)</ref> If {{math|1=''L''(''n'')}} is the length of the shortest Lucas chain for {{mvar|n}}, then Kutz has shown that most {{mvar|n}} do not have {{math|1=''L'' < (1-ε) log<sub>φ</sub>(''n'')}}, where φ is the Golden ratio.<ref name=G169/>
== References == {{Reflist}} * {{cite book |last=Guy | first=Richard K. | authorlink=Richard K. Guy | title=Unsolved problems in number theory | publisher=Springer-Verlag |edition=3rd | year=2004 |isbn=978-0-387-20860-2 | zbl=1058.11001 | pages=169–171 }} * {{cite journal|first=Martin | last=Kutz |title=Lower Bounds For Lucas Chains |journal=SIAM J. Comput. |year=2002 |volume=31 | number= 6 |pages= 1896–1908 |url=http://www.mpi-inf.mpg.de/~mkutz/pubs/Kutz_LucasChains.pdf | zbl=1055.11077 | doi=10.1137/s0097539700379255}} * {{Cite journal|first=Peter L. | last=Montgomery | authorlink=Peter Montgomery (mathematician) | title=Evaluating Recurrences of Form ''X''<sub>''m+n''</sub> = ''f(X''<sub>''m''</sub>, ''X''<sub>''n''</sub>, ''X''<sub>''m-n''</sub>) Via Lucas Chains | year=1983 | journal=Unpublished|url=http://cr.yp.to/bib/1992/montgomery-lucas.ps |format=PS }}
{{DEFAULTSORT:Lucas Chain}} Category:Integer sequences Category:Addition chains