Editing Lucas chain (section)

{{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/>