login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003064 a(n) = smallest number with shortest addition chain of length n.
(Formerly M0667)
8

%I M0667 #54 Aug 23 2023 10:49:38

%S 1,2,3,5,7,11,19,29,47,71,127,191,379,607,1087,1903,3583,6271,11231,

%T 18287,34303,65131,110591,196591,357887,685951,1176431,2211837,

%U 4169527,7624319,14143037,25450463,46444543,89209343,155691199

%N a(n) = smallest number with shortest addition chain of length n.

%C An addition chain of length n for a number a is a sequence 1 = a_0, a_1,..., a_n = a such that for each i>0, a_i is the sum of two (not necessarily distinct) elements of the sequence. - _Glen Whitney_, Nov 09 2021

%C The largest number with an addition chain of length n is 2^n. This chain is of course shortest for 2^n. - _Franklin T. Adams-Watters_, Jan 20 2016

%C The step from a_{i-1} to a_i is called "small" if a_i is less than the smallest power of two greater than a_{i-1}. The sequence b(n) of the smallest number which requires n small steps in an addition chain is a subsequence of this sequence, starting a(0), a(2), a(4), a(7), a(10), a(15), a(21), a(28), a(37), a(46),... - _Glen Whitney_, Nov 09 2021

%D D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 2, p. 458; Vol. 2, 3rd. ed., p. 477.

%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="/A003064/b003064.txt">Table of n, a(n) for n = 0..46</a> (Terms 0..41 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. 60.

%H Swee Hong Chan and Igor Pak, <a href="https://arxiv.org/abs/2308.10214">Computational complexity of counting coincidences</a>, arXiv:2308.10214 [math.CO], 2023. See p. 10.

%H M. Elia and F. Neri, <a href="http://dx.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. The smallest number with an addition chain of length n is denoted c(n) in this paper.

%H Achim Flammenkamp, <a href="http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html">Shortest addition chains</a>

%H D. Knuth, <a href="/A003063/a003063.pdf">Letter to N. J. A. Sloane, date unknown</a>

%H <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>

%e a(7) = 29 because 29 is the smallest number with a shortest addition chain requiring 7 additions. An example of a shortest addition chain for 29 is (1 2 3 4 7 11 18 29).

%Y This is the "smallest inverse" of A003313. Cf. A003065.

%Y Cf. A075530, A115617 [Smallest number for which Knuth's power tree method produces an addition chain of length n].

%K nonn,nice,hard

%O 0,2

%A _N. J. A. Sloane_ and _Don Knuth_

%E New terms from _Achim Flammenkamp_, Math. Diplomarbeit, Univ. Bielefeld, 1991; and from Daniel Bleichenbacher (bleichen(AT)inf.ethz.ch)

%E a(25)-a(27) from the 3rd. ed. of Knuth vol. 2, sent by David Moulton, Jun 24 2003

%E a(28)-a(30) from _Achim Flammenkamp_'s web site, Feb 01 2005

%E a(31) computed Dec 15 2005 by _Neill M. Clift_. - _Hugo Pfoertner_, Jan 29 2006

%E a(32) from _Neill M. Clift_, Jun 15 2007

%E a(33)-a(34) from _Neill M. Clift_, May 21 2008

%E b-file up to a(41) extracted from _Achim Flammenkamp_'s web site. - _R. J. Mathar_, May 14 2013

%E b-file updated to a(46) from _Achim Flammenkamp_'s web site. - _Glen Whitney_, Nov 09 2021

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 18:04 EDT 2024. Contains 371254 sequences. (Running on oeis4.)