%I M0707 #41 Nov 11 2021 20:11:27
%S 1,1,2,3,5,9,15,26,44,78,136,246,432,772,1382,2481,4490,8170,14866,
%T 27128,49544,90371,165432,303475,558275,1028508,1896704,3501029,
%U 6465774,11947258,22087489,40886910,75763102,140588339
%N Number of integers with a shortest addition chain of length n.
%D D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 2, p. 459.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D See A003313 for a much more extensive list of references and links.
%H Glen Whitney, <a href="/A003065/b003065.txt">Table of n, a(n) for n = 0..44</a> (Terms 0..38 from R. J. Mathar)
%H Daniel Bleichenbacher, <a href="http://cr.yp.to/bib/1996/bleichenbacher-thesis.ps">Efficiency and Security of Cryptosystems based on Number Theory</a>, PhD Thesis, Diss. ETH No. 11404, Zürich 1996. See p. 61.
%H M. Elia and F. Neri, <a href="https://doi.org/10.1007/978-1-4612-3352-7_13">A note on addition chains and some related conjectures</a>, pp. 166-181 of R. M. Capocelli, ed., Sequences, Springer-Verlag, NY 1990.
%H Achim Flammenkamp, <a href="http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html">Shortest addition chains</a>
%H <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%e 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.
%Y Cf. A003064, A003313.
%Y Cf. A114623 [Number of integers for which Knuth's power tree method produces an addition chain of length n].
%K nonn,nice,hard
%O 0,3
%A _N. J. A. Sloane_, _Don Knuth_
%E Updated through a(28) from _Achim Flammenkamp_'s web site Feb 01 2005
%E a(28) corrected from 6465773 to 6465774, based on information received from _Neill M. Clift_. - _Hugo Pfoertner_, Jan 29 2006
%E a(29)-a(30) from _Neill M. Clift_, Jun 15 2007
%E a(31)-a(33) from _Neill M. Clift_, May 21 2008
%E b-file up to a(38) extracted from _Achim Flammenkamp_'s web site. _R. J. Mathar_, May 14 2013
%E b-file updated to a(44) from _Achim Flammenkamp_'s web site. _Glen Whitney_, Nov 09 2021