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

1, 2, 3, 5, 7, 11, 19, 29, 47, 71, 127, 191, 379, 607, 1087, 1903, 3583, 6271, 11231, 18287, 34303, 65131, 110591, 196591, 357887, 685951, 1176431, 2211837, 4169527, 7624319, 14143037, 25450463, 46444543, 89209343, 155691199, 298695487, 550040063, 994660991

Offset: 0

Author

N. J. A. Sloane and Don Knuth

Keywords

• nonn
• nice
• hard

Comments

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

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

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

Examples

			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).
		

References

• D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 2, p. 458; Vol. 2, 3rd. ed., p. 477.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• See A003313 for a much more extensive list of references and links.

Links

• Glen Whitney, Table of n, a(n) for n = 0..46 (Terms 0..41 from R. J. Mathar)
• Daniel Bleichenbacher, Efficiency and Security of Cryptosystems based on Number Theory, PhD Thesis, Diss. ETH No. 11404, Zürich 1996. See p. 60.
• Swee Hong Chan and Igor Pak, Computational complexity of counting coincidences, arXiv:2308.10214 [math.CO], 2023. See p. 10.
• M. Elia and F. Neri, A note on addition chains and some related conjectures, 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.
• Achim Flammenkamp, Shortest addition chains
• D. Knuth, Letter to N. J. A. Sloane, date unknown
• Index to sequences related to the complexity of n

Crossrefs

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

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

Extensions

New terms from Achim Flammenkamp, Math. Diplomarbeit, Univ. Bielefeld, 1991; and from Daniel Bleichenbacher (bleichen(AT)inf.ethz.ch)

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

a(28)-a(30) from Achim Flammenkamp's web site, Feb 01 2005

a(31) computed Dec 15 2005 by Neill M. Clift. - Hugo Pfoertner, Jan 29 2006

a(32) from Neill M. Clift, Jun 15 2007

a(33)-a(34) from Neill M. Clift, May 21 2008

b-file up to a(41) extracted from Achim Flammenkamp's web site. - R. J. Mathar, May 14 2013

b-file updated to a(46) from Achim Flammenkamp's web site. - Glen Whitney, Nov 09 2021