|
| |
|
|
A003064
|
|
a(n) = smallest number with shortest 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
|
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
|
|
|
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
|
|
|
|
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
|
Cf. A075530, A115617 [Smallest number for which Knuth's power tree method produces an addition chain of length n].
|
|
|
KEYWORD
|
nonn,nice,hard
|
|
|
AUTHOR
|
|
|
|
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
|
|
|
STATUS
|
approved
|
| |
|
|
