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

Author

N. J. A. Sloane, May 23 2008

Keywords

• nonn

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.

Extensions

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