Editing Lucas chain

{{Short description|A 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]] 

:''a''<sub>0</sub>, ''a''<sub>1</sub>, ''a''<sub>2</sub>, ''a''<sub>3</sub>, ...

that satisfies

:''a''<sub>0</sub>=1, 

and 
:for each ''k'' > 0: ''a''<sub>''k''</sub> = ''a''<sub>''i''</sub> + ''a''<sub>''j''</sub>, and either ''a''<sub>''i''</sub> = ''a''<sub>''j''</sub> or  |''a''<sub>''i''</sub> &minus; ''a''<sub>''j''</sub>| = ''a''<sub>''m''</sub>, for some ''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 (mathematician)|Peter Montgomery]] in 1983.<ref>Kutz (2002)</ref>  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<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]]