|
|
A003065
|
|
Number of integers with a shortest addition chain of length n.
(Formerly M0707)
|
|
7
|
|
|
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;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
REFERENCES
|
D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 2, p. 459.
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.
|
|
LINKS
|
|
|
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. A114623 [Number of integers for which Knuth's power tree method produces an addition chain of length n].
|
|
KEYWORD
|
nonn,nice,hard
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|