%I A003065 M0707
%S A003065 1,1,2,3,5,9,15,26,44,78,136,246,432,772,1382,2481,4490,8170,14866,
%T A003065 27128,49544,90371,165432,303475,558275,1028508,1896704,3501029,6465774,
%U A003065 11947258,22087489,40886910,75763102,140588339
%N A003065 Number of integers with an addition chain of length n.
%D A003065 M. Elia and F. Neri, A note on addition chains ..., pp. 166-181 of R. 
               M. Capocelli, ed., Sequences, Springer-Verlag, NY 1990.
%D A003065 D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, 
               MA, Vol. 2, p. 459.
%D A003065 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A003065 See A003313 for a much more extensive list of references and links.
%H A003065 Daniel Bleichenbacher, <a href="http://www.bell-labs.com/user/bleichen/
               diss/thesis.html">Efficiency and Security of Cryptosystems based 
               on Number Theory.</a> PhD Thesis, Diss. ETH No. 11404, Zuerich 1996. 
               See p. 61.
%H A003065 Achim Flammenkamp, <a href="http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html">
               Shortest addition chains</a>
%e A003065 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 A003065 Cf. A003064, A003313.
%Y A003065 Cf. A114623 [Number of integers for which Knuth's power tree method produces 
               an addition chain of length n].
%Y A003065 Sequence in context: A114140 A096816 A018157 this_sequence A005169 A129852 
               A065954
%Y A003065 Adjacent sequences: A003062 A003063 A003064 this_sequence A003066 A003067 
               A003068
%K A003065 nonn,nice,hard
%O A003065 0,3
%A A003065 N. J. A. Sloane (njas(AT)research.att.com), D. E. Knuth
%E A003065 Updated through a(28) from the Flammenkamp web site Feb 01 2005.
%E A003065 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
%E A003065 a(29)=11947258 and a(30)=22087489 computed by N. Clift (neillclift(AT)msn.com), 
               Jun 15 2007
%E A003065 40886910, 75763102, 140588339 from N. Clift (neillclift(AT)msn.com), 
               May 21 2008