This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A003313 M0255 #175 Feb 16 2025 08:32:27 %S A003313 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, %T A003313 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, %U A003313 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 %N A003313 Length of shortest addition chain for n. %C A003313 Equivalently, minimal number of multiplications required to compute the n-th power. %D A003313 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 A003313 D. Bleichenbacher and A. Flammenkamp, An Efficient Algorithm for Computing Shortest Addition Chains, Preprint, 1997. %D A003313 A. Flammenkamp, Drei Beitraege zur diskreten Mathematik: Additionsketten, No-Three-in-Line-Problem, Sociable Numbers, Diplomarbeit, Bielefeld 1991. %D A003313 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. %D A003313 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 A003313 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 A003313 D. E. Knuth, website, further updates to Vol. 2 of TAOCP. %D A003313 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. %D A003313 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence). %H A003313 D. W. Wilson and Antoine Mathys, <a href="/A003313/b003313.txt">Table of n, a(n) for n = 1..100000</a> (10001 terms from D. W. Wilson) %H A003313 F. Bergeron, J. Berstel, S. Brlek, and C. Duboc, <a href="http://dx.doi.org/10.1016/0196-6774(89)90036-9">Addition chains using continued fractions</a>, J. Algorithms 10 (1989), 403-412. %H A003313 Wawrzyniec Bieniawski, Piotr Masierak, Andrzej Tomski, and Szymon Łukaszyk, <a href="https://www.preprints.org/manuscript/202409.1581">Assembly Theory - Formalizing Assembly Spaces and Discovering Patterns and Bounds</a>, Preprints.org (2025). %H A003313 Daniel Bleichenbacher, <a href="http://www.bell-labs.com/user/bleichen/diss/thesis.html">Efficiency and Security of Cryptosystems based on Number Theory.</a> PhD Thesis, Diss. ETH No. 11404, Zürich 1996. See p. 61. %H A003313 Alfred Brauer, <a href="http://dx.doi.org/10.1090/S0002-9904-1939-07068-7">On addition chains</a> Bull. Amer. Math. Soc. 45, (1939). 736-739. %H A003313 John M. Campbell, <a href="https://arxiv.org/abs/2403.20073">A binary version of the Mahler-Popken complexity function</a>, arXiv:2403.20073 [math.NT], 2024. See pp. 3-4. See also <a href="https://math.colgate.edu/~integers/y94/y94.pdf">Integers</a> (2024) Vol. 24, Art. No. A94. See pp. 3, 10. %H A003313 Peter Downey, Benton Leong, and Ravi Sethi, <a href="http://dx.doi.org/10.1137/0210047">Computing sequences with addition chains</a> SIAM J. Comput. 10 (1981), 638-646. %H A003313 M. Elia and F. Neri, <a href="https://doi.org/10.1007/978-1-4612-3352-7_13">A note on addition chains and some related conjectures</a>, (Naples/Positano, 1988), pp. 166-181 of R. M. Capocelli, ed., Sequences, Springer-Verlag, NY 1990. %H A003313 Christian Elsholtz et al., <a href="http://mathoverflow.net/questions/217411/upper-bound-on-length-of-addition-chain/218608#218608">Upper bound on length of addition chain</a>, Math Overflow, Sep 18 2015. %H A003313 P. Erdős, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa6/aa618.pdf">Remarks on number theory. III. On addition chains</a>, Acta Arith. 6 1960 77-81. %H A003313 Achim Flammenkamp, <a href="http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html">Shortest addition chains</a> %H A003313 A. A. Gioia, M. V. Subbarao, and M. Sugunamma, <a href="http://dx.doi.org/10.1215/S0012-7094-62-02948-4">The Scholz-Brauer problem in addition chains</a>, Duke Math. J. 29 1962 481-487. %H A003313 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, <a href="https://arxiv.org/abs/1806.02059">Problems and solutions of the Fourth International Students' Olympiad in Cryptography NSUCRYPTO</a>, arXiv:1806.02059 [cs.CR], 2018. %H A003313 R. L. Graham, A. C.-C. Yao, and F. F. Yao, <a href="http://dx.doi.org/10.1016/0012-365X(78)90111-5">Addition chains with multiplicative cost</a> Discrete Math. 23 (1978), 115-119. %H A003313 D. Knuth, <a href="/A003063/a003063.pdf">Letter to N. J. A. Sloane, date unknown</a> %H A003313 D. E. Knuth, <a href="http://www-cs-faculty.stanford.edu/~knuth/programs.html">See the achain-all program</a> %H A003313 D. P. McCarthy, <a href="http://www.jstor.org/stable/2007998">Effect of improved multiplication efficiency on exponentiation algorithms derived from addition chains</a> Math. Comp. 46 (1986), 603-608. %H A003313 Alec Mihailovs, <a href="/A003313/a003313b.txt">Notes on using Flammenkamp's tables</a> %H A003313 Jorge Olivos, <a href="http://dx.doi.org/10.1016/0196-6774(81)90003-1">On vectorial addition chains</a> J. Algorithms 2 (1981), 13-21. %H A003313 Hugo Pfoertner, <a href="/A003313/a003313.txt">Addition chains</a> %H A003313 Kari Ragnarsson and Bridget Eileen Tenner, <a href="http://arxiv.org/abs/0802.2550">Obtainable Sizes of Topologies on Finite Sets</a>, arXiv:0802.2550 [math.CO], 2008-2009; Journal of Combinatorial Theory, Series A 117 (2010) 138-151. %H A003313 Arnold Schönhage, <a href="http://dx.doi.org/10.1016/0304-3975(75)90008-0">A lower bound for the length of addition chains</a> Theor. Comput. Sci. 1 (1975), 1-12. %H A003313 Edward G. Thurber, <a href="http://projecteuclid.org/euclid.pjm/1102945286">The Scholz-Brauer problem on addition chains</a> Pacific J. Math. 49 (1973), 229-242. %H A003313 Edward G. Thurber, <a href="http://dx.doi.org/10.1215/S0012-7094-73-04085-4">On addition chains l(mn)<=l(n)-b and lower bounds for c(r)</a> Duke Math. J. 40 (1973), 907-913. %H A003313 Edward G. Thurber, <a href="http://dx.doi.org/10.1016/0012-365X(76)90105-9">Addition chains and solutions of l(2n)=l(n) and l(2^n-1)=n+l(n)-1</a>, Discrete Math., Vol. 16 (1976), 279-289. %H A003313 Edward G. Thurber, <a href="http://dx.doi.org/10.1016/0012-365X(93)90303-B">Addition chains-an erratic sequence</a> Discrete Math. 122 (1993), 287-305. %H A003313 Edward G. Thurber, <a href="http://dx.doi.org/10.1137/S0097539795295663">Efficient generation of minimal length addition chains</a>, SIAM J. Comput. 28 (1999), 1247-1263. %H A003313 W. R. Utz, <a href="http://dx.doi.org/10.1090/S0002-9939-1953-0054618-X">A note on the Scholz-Brauer problem in addition chains</a>, Proc. Amer. Math. Soc. 4, (1953). 462-463. %H A003313 Emanuel Vegh, <a href="http://dx.doi.org/10.1016/0097-3165(75)90098-9">A note on addition chains</a>, J. Combinatorial Theory Ser. A 19 (1975), 117-118. %H A003313 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/AdditionChain.html">Addition Chain</a>. %H A003313 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/ScholzConjecture.html">Scholz Conjecture</a>. %H A003313 C. T. Whyburn, <a href="http://dx.doi.org/10.1090/S0002-9939-1965-0180517-7">A note on addition chains</a> Proc. Amer. Math. Soc. 16 1965 1134. %H A003313 <a href="/index/Com#complexity">Index to sequences related to the complexity of n</a> %F A003313 a(n*m) <= a(n)+a(m). In particular, a(n^k) <= k * a(n). - _Max Alekseyev_, Jul 22 2005 %F A003313 For all n >= 2, a(n) <= (4/3)*floor(log_2 n) + 2. - _Jonathan Vos Post_, Oct 08 2008 %F A003313 From _Achim Flammenkamp_, Oct 26 2016: (Start) %F A003313 a(n) <= 9/log_2(71) log_2(n), for all n. %F A003313 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) %F A003313 a(n) <= A014701(n). - _Charles R Greathouse IV_, Jan 03 2018 %F A003313 From _Szymon Lukaszyk_, Apr 05 2024: (Start) %F A003313 For n = 2^s, a(n)=s; %F A003313 for n = 2^s + 2^m, m in [0..s-1] (A048645), a(n)=s+1; %F A003313 for n = 2^s + 3*2^m, m in [0..s-2] (A072823), a(n)=s+2; %F A003313 for n = 2^s + 7*2^(s-3), s>2 (A072823), a(n)=s+2.(End) %e A003313 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.) %e A003313 1 %e A003313 | %e A003313 2 %e A003313 / \ %e A003313 / \ %e A003313 / \ %e A003313 / \ %e A003313 / \ %e A003313 3 4 %e A003313 / \ \ %e A003313 / \ \ %e A003313 / \ \ %e A003313 / \ \ %e A003313 5 6 8 %e A003313 / \ | / \ %e A003313 / \ | / \ %e A003313 7 10 12 9 16 %e A003313 / / \ / \ / \ / \ %e A003313 14 11 20 15 24 13 17 18 32 %e A003313 E.g., a(15) = 5 and an optimal chain for 15 is 1, 2, 3, 6, 12, 15. %e A003313 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. %Y A003313 Cf. A003064, A003065, A005766, A014701, A079300, A230528. %K A003313 nonn,nice,look %O A003313 1,3 %A A003313 _N. J. A. Sloane_ %E A003313 More terms from _Jud McCranie_, Nov 01 2001