The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003065 Number of integers with a shortest addition chain of length n.
(Formerly M0707)

%I M0707

%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 R. J. Mathar, <a href="/A003065/b003065.txt">Table of n, a(n) for n = 0..38</a>

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 25 00:32 EDT 2021. Contains 346273 sequences. (Running on oeis4.)