

A003064


Smallest number with minimal addition chain of length n.
(Formerly M0667)


8



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

The largest number with an addition chain of length n is 2^n. This chain is of course minimal for 2^n.  Franklin T. AdamsWatters, Jan 20 2016


REFERENCES

D. E. Knuth, The Art of Computer Programming. AddisonWesley, 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

R. J. Mathar, Table of n, a(n) for n = 0..41
Daniel Bleichenbacher, Efficiency and Security of Cryptosystems based on Number Theory. PhD Thesis, Diss. ETH No. 11404, Zuerich 1996. See p. 60.
M. Elia and F. Neri, A note on addition chains and some related conjectures, pp. 166181 of R. M. Capocelli, ed., Sequences, SpringerVerlag, NY 1990. The smallest number with an addition chain of length n is n.
Achim Flammenkamp, Shortest addition chains
D. Knuth, Letter to N. J. A. Sloane, date unknown
Index to sequences related to the complexity of The smallest number with an addition chain of length n is n.n


EXAMPLE

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


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].
Sequence in context: A158069 A039726 A115617 * A057429 A137814 A065726
Adjacent sequences: A003061 A003062 A003063 * A003065 A003066 A003067


KEYWORD

nonn,nice,hard


AUTHOR

N. J. A. Sloane and Don Knuth


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 the Flammenkamp web site, Feb 01 2005
a(31)=25450463 computed Dec 15 2005 by N. Clift (neillclift(AT)msn.com).  Hugo Pfoertner, Jan 29 2006
a(32)=46444543 computed by N. Clift (neillclift(AT)msn.com), Jun 15 2007
89209343 and 155691199 from N. Clift (neillclift(AT)msn.com), May 21 2008
bfile up to a(41) extracted from Flammenkamp's web site.  R. J. Mathar, May 14 2013


STATUS

approved



