login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. Adams-Watters, Jan 20 2016

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

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. 166-181 of R. M. Capocelli, ed., Sequences, Springer-Verlag, 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

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

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified June 28 20:39 EDT 2017. Contains 288840 sequences.