|
| |
|
|
A003313
|
|
Length of shortest addition chain for n.
(Formerly M0255)
|
|
59
|
|
|
|
0, 1, 2, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 5, 5, 6, 5, 6, 6, 6, 5, 6, 6, 6, 6, 7, 6, 7, 5, 6, 6, 7, 6, 7, 7, 7, 6, 7, 7, 7, 7, 7, 7, 8, 6, 7, 7, 7, 7, 8, 7, 8, 7, 8, 8, 8, 7, 8, 8, 8, 6, 7, 7, 8, 7, 8, 8, 9, 7, 8, 8, 8, 8, 8, 8, 9, 7, 8, 8, 8, 8, 8, 8, 9, 8, 9, 8, 9, 8, 9, 9, 9, 7, 8, 8, 8, 8
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
COMMENTS
|
Equivalently, minimal number of multiplications required to compute the n-th power.
|
|
|
REFERENCES
|
Hatem M. Bahig, Mohamed H. El-Zahar, and Ken Nakamula, Some results for some conjectures in addition chains, in Combinatorics, computability and logic, pp. 47-54, Springer Ser. Discrete Math. Theor. Comput. Sci., Springer, London, 2001.
D. Bleichenbacher and A. Flammenkamp, An Efficient Algorithm for Computing Shortest Addition Chains, Preprint, 1997.
A. Flammenkamp, Drei Beitraege zur diskreten Mathematik: Additionsketten, No-Three-in-Line-Problem, Sociable Numbers, Diplomarbeit, Bielefeld 1991.
S. B. Gashkov and V. V. Kochergin, On addition chains of vectors, gate circuits and the complexity of computations of powers [translation of Metody Diskret. Anal. No. 52 (1992), 22-40, 119-120; 1265027], Siberian Adv. Math. 4 (1994), 1-16.
A. A. Gioia and M. V. Subbarao, The Scholz-Brauer problem in addition chains, II, in Proceedings of the Eighth Manitoba Conference on Numerical Mathematics and Computing (Univ. Manitoba, Winnipeg, Man., 1978), pp. 251-274, Congress. Numer., XXII, Utilitas Math., Winnipeg, Man., 1979.
D. E. Knuth, The Art of Computer Programming, vol. 2, Seminumerical Algorithms, 2nd ed., Fig. 14 on page 403; 3rd edition, 1998, p. 465.
D. E. Knuth, website, further updates to Vol. 2 of TAOCP.
Michael O. Rabin and Shmuel Winograd, "Fast evaluation of polynomials by rational preparation." Communications on Pure and Applied Mathematics 25.4 (1972): 433-458. See Table p. 455.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
Anastasiya Gorodilova, Sergey Agievich, Claude Carlet, Evgeny Gorkunov, Valeriya Idrisova, Nikolay Kolomeec, Alexandr Kutsenko, Svetla Nikova, Alexey Oblaukhov, Stjepan Picek, Bart Preneel, Vincent Rijmen, Natalia Tokareva, Problems and solutions of the Fourth International Students' Olympiad in Cryptography NSUCRYPTO, arXiv:1806.02059 [cs.CR], 2018.
|
|
|
FORMULA
|
a(n*m) <= a(n)+a(m). In particular, a(n^k) <= k * a(n). - Max Alekseyev, Jul 22 2005
a(n) <= 9/log_2(71) log_2(n), for all n.
It is conjectured by D. E. Knuth, K. Stolarsky et al. that for all n: floor(log_2(n)) + ceiling(log_2(v(n))) <= a(n). (End)
For n = 2^s, a(n)=s;
for n = 2^s + 2^m, m in [0..s-1] (A048645), a(n)=s+1;
for n = 2^s + 3*2^m, m in [0..s-2] (A072823), a(n)=s+2;
for n = 2^s + 7*2^(s-3), s>2 (A072823), a(n)=s+2.(End)
|
|
|
EXAMPLE
|
For n < 149 and for many higher values of n, a(n) is the depth of n in a tree whose first 6 levels are shown below. The path from the root of the tree to n gives an optimal addition chain. (See Knuth, Vol. 2, Sect. 4.6.3, Fig. 14 and Ex. 5.)
1
|
2
/ \
/ \
/ \
/ \
/ \
3 4
/ \ \
/ \ \
/ \ \
/ \ \
5 6 8
/ \ | / \
/ \ | / \
7 10 12 9 16
/ / \ / \ / \ / \
14 11 20 15 24 13 17 18 32
E.g., a(15) = 5 and an optimal chain for 15 is 1, 2, 3, 6, 12, 15.
It is not possible to extend the tree to include the optimal addition chains for all n. For example, the chains for 43, 77, and 149 are incompatible. See the link to Achim Flammenkamp's web page on addition chains.
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
