cp's OEIS Frontend

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

%I A003064 M0667 #57 Apr 10 2025 06:46:34
%S A003064 1,2,3,5,7,11,19,29,47,71,127,191,379,607,1087,1903,3583,6271,11231,
%T A003064 18287,34303,65131,110591,196591,357887,685951,1176431,2211837,
%U A003064 4169527,7624319,14143037,25450463,46444543,89209343,155691199,298695487,550040063,994660991
%N A003064 a(n) = smallest number with shortest addition chain of length n.
%C A003064 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 A003064 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 A003064 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 A003064 D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 2, p. 458; Vol. 2, 3rd. ed., p. 477.
%D A003064 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A003064 See A003313 for a much more extensive list of references and links.
%H A003064 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 A003064 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 A003064 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 A003064 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 A003064 Achim Flammenkamp, <a href="http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html">Shortest addition chains</a>
%H A003064 D. Knuth, <a href="/A003063/a003063.pdf">Letter to N. J. A. Sloane, date unknown</a>
%H A003064 <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a>
%e A003064 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 A003064 This is the "smallest inverse" of A003313. Cf. A003065.
%Y A003064 Cf. A075530, A115617 [Smallest number for which Knuth's power tree method produces an addition chain of length n].
%K A003064 nonn,nice,hard
%O A003064 0,2
%A A003064 _N. J. A. Sloane_ and _Don Knuth_
%E A003064 New terms from _Achim Flammenkamp_, Math. Diplomarbeit, Univ. Bielefeld, 1991; and from Daniel Bleichenbacher (bleichen(AT)inf.ethz.ch)
%E A003064 a(25)-a(27) from the 3rd. ed. of Knuth vol. 2, sent by David Moulton, Jun 24 2003
%E A003064 a(28)-a(30) from _Achim Flammenkamp_'s web site, Feb 01 2005
%E A003064 a(31) computed Dec 15 2005 by _Neill M. Clift_. - _Hugo Pfoertner_, Jan 29 2006
%E A003064 a(32) from _Neill M. Clift_, Jun 15 2007
%E A003064 a(33)-a(34) from _Neill M. Clift_, May 21 2008
%E A003064 b-file up to a(41) extracted from _Achim Flammenkamp_'s web site. - _R. J. Mathar_, May 14 2013
%E A003064 b-file updated to a(46) from _Achim Flammenkamp_'s web site. - _Glen Whitney_, Nov 09 2021