Lucas chain

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

for each k > 0: ak = ai + aj, and either ai = aj or |ai aj| = am, for some i, j, m < k.[1][2]

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. Guy (2004) p.169
  2. Weisstein, Eric W. "Lucas Chain". mathworld.wolfram.com. Retrieved 2020-08-11.
  3. Kutz (2002)
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.