A105195 Length of shortest simple Lucas chain for n.

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

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.

(i) a(4) is given as 2 in Table 5.1 of the reference, which probably is a typographical error since the length of the example obviously is the same as for a(5).

(ii) Other authors call a(n)+1 the length of the chain, i.e., they include the first 1 of the chain in the count. - R. J. Mathar, May 24 2008

Examples

			Chain for n=11: (1,2,3,4,7,11), length 5. Chain for n=12: (1,2,3,5,7,12), length 5.
Chain for n=13: (1,2,3,5,8,13), length 5. Chain for n=14: (1,2,3,4,5,9,14), length 6. - _R. J. Mathar_, May 24 2008
		

Links

• 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.
• Index to sequences related to the complexity of n

Crossrefs

Cf. A003313, A104892, A105096, A266082.

Extensions

a(11)-a(36) added by R. J. Mathar, May 24 2008

a(1) prepended by and a(37)-a(85) from Jinyuan Wang, Apr 18 2025