|
Search: id:A003065
|
|
|
| A003065 |
|
Number of integers with an addition chain of length n.
(Formerly M0707)
|
|
+0
5
|
|
| 1, 1, 2, 3, 5, 9, 15, 26, 44, 78, 136, 246, 432, 772, 1382, 2481, 4490, 8170, 14866, 27128, 49544, 90371, 165432, 303475, 558275, 1028508, 1896704, 3501029, 6465774, 11947258, 22087489, 40886910, 75763102, 140588339
(list; graph; listen)
|
|
|
OFFSET
|
0,3
|
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
See A003313 for a much more extensive list of references and links.
M. Elia and F. Neri, A note on addition chains ..., pp. 166-181 of R. M. Capocelli, ed., Sequences, Springer-Verlag, NY 1990.
D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 2, p. 459.
|
|
LINKS
|
Daniel Bleichenbacher, Efficiency and Security of Cryptosystems based on Number Theory. PhD Thesis, Diss. ETH No. 11404, Zuerich 1996. See p. 61.
Achim Flammenkamp, Shortest addition chains
|
|
EXAMPLE
|
a(6) = 15 because 15 numbers have shortest addition chains involving 6 additions. These numbers are 19,21,22,23,25,26,27,28,30,33,34,36,40,48,64.
|
|
CROSSREFS
|
Cf. A003064, A003313.
Cf. A114623 [Number of integers for which Knuth's power tree method produces an addition chain of length n].
Adjacent sequences: A003062 A003063 A003064 this_sequence A003066 A003067 A003068
Sequence in context: A114140 A096816 A018157 this_sequence A005169 A129852 A065954
|
|
KEYWORD
|
nonn,nice,hard
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com), D. E. Knuth
|
|
EXTENSIONS
|
Updated through a(28) from the Flammenkamp web site Feb 01 2005.
a(28) corrected from 6465773 to 6465774, based on information received from N. Clift (neillclift(AT)msn.com). - Hugo Pfoertner (hugo(AT)pfoertner.org), Jan 29 2006
a(29)=11947258 and a(30)=22087489 computed by N. Clift (neillclift(AT)msn.com), Jun 15 2007
40886910, 75763102, 140588339 from N. Clift (neillclift(AT)msn.com), May 21 2008
|
|
|
Search completed in 0.002 seconds
|
