A105195 Length of shortest simple Lucas chain for n.

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

Offset

2,2

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

Links

Table of n, a(n) for n=2..36.

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

Index to sequences related to the complexity of n

Example

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

Crossrefs

Cf. A104892, A105096, A003313.

Sequence in context: A213711 A072649 A266082 * A257569 A039836 A083398

Adjacent sequences: A105192 A105193 A105194 * A105196 A105197 A105198

Keyword

nonn

Author

N. J. A. Sloane, May 23 2008

Extensions

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

Status

approved