In
mathematics, a Lucas chain is a restricted type of
addition chain In mathematics, an addition chain for computing a positive integer can be given by a sequence of natural numbers starting with 1 and ending with , such that each number in the sequence is the sum of two previous numbers. The ''length'' of an additi ...
, named for the French mathematician
Édouard Lucas
__NOTOC__
François Édouard Anatole Lucas (; 4 April 1842 – 3 October 1891) was a French mathematician. Lucas is known for his study of the Fibonacci sequence. The related Lucas sequences and Lucas numbers are named after him.
Biography
Lucas ...
. It is a
sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is calle ...
:''a''
0, ''a''
1, ''a''
2, ''a''
3, ...
that satisfies
:''a''
0=1,
and
:for each ''k'' > 0: ''a''
''k'' = ''a''
''i'' + ''a''
''j'', and either ''a''
''i'' = ''a''
''j'' or , ''a''
''i'' − ''a''
''j'', = ''a''
''m'', for some ''i'', ''j'', ''m'' < ''k''.
[Guy (2004) p.169]
The sequence of powers of 2 (1, 2, 4, 8, 16, ...) and the
Fibonacci sequence
In mathematics, the Fibonacci numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...
(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.
[Kutz (2002)] 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
In mathematics, two quantities are in the golden ratio if their ratio is the same as the ratio of their sum to the larger of the two quantities. Expressed algebraically, for quantities a and b with a > b > 0,
where the Greek letter phi ( ...
.
[
]
References
*
*
*
{{DEFAULTSORT:Lucas Chain
Integer sequences
Addition chains