A105096 Length of shortest Lucas chain for n.

0, 1, 2, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 6, 5, 6, 5, 6, 6, 7, 5, 6, 6, 6, 6, 7, 6, 7, 5, 7, 7, 7, 6, 8, 7, 7, 6, 8, 7, 8, 7, 7, 8, 8, 6, 8, 7, 8, 7, 9, 7, 8, 7, 8, 8, 9, 7, 9, 8, 8, 6, 8, 8, 9, 8, 9, 8, 9, 7, 9, 9, 8, 8, 9, 8, 9, 7, 8, 9, 10, 8, 9, 9, 9

Offset

1,3

Comments

Lucas chains are addition chains with additional requirements on the presence of differences between members of the chain. Therefore a(n) >= A003313(n) and A104892(n) <= A003064(n). Shortest simple Lucas chains are constrained even further (forbid duplication between adjacent members). Therefore a(n) <= A105195(n). - R. J. Mathar, May 24 2008

Links

Jinyuan Wang, Table of n, a(n) for n = 1..10000

Daniel Bleichenbacher, Efficiency and Security of Cryptosystems based on Number Theory. PhD Thesis, Diss. ETH No. 11404, Zuerich 1996. See p. 64.

Neill Clift, Lucas/Differential Addition Chains.

Wikipedia, Lucas chain.

Index to sequences related to the complexity of n

Crossrefs

Cf. A003313, A104892, A105195, A266082.

Sequence in context: A117497 A117498 A064097 * A014701 A207034 A226164

Adjacent sequences: A105093 A105094 A105095 * A105097 A105098 A105099

Keyword

nonn

Author

N. J. A. Sloane, May 23 2008

Extensions

Offset changed to 1 and more terms from Jinyuan Wang, Apr 18 2025

Status

approved