%I A003313 M0255
%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,7,
%T A003313 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,
%U A003313 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 n-th 
               power.
%C A003313 Equivalently, for n>1, the minimum number of points m(n) needed to make 
               a topology having n open sets, as shown in Table 1, p.2 of Ragnarsson 
               and Tenner. [From Jonathan Vos Post (jvospost3(AT)gmail.com), Oct 
               08 2008]
%D A003313 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A003313 Bahig, Hatem M.; El-Zahar, Mohamed H.; Nakamula, Ken; 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 Bergeron, F.; Berstel, J.; Brlek, S.; Duboc, C.; Addition chains using 
               continued fractions. J. Algorithms 10 (1989), 403-412.
%D A003313 D. Bleichenbacher, Efficiency and Security of Cryptosystems based on 
               Number Theory, Dissertation, ETH Zurich 1996.
%D A003313 D. Bleichenbacher and A. Flammenkamp, An Efficient Algorithm for Computing 
               Shortest Addition Chains, Preprint, 1997.
%D A003313 Brauer, Alfred, On addition chains. Bull. Amer. Math. Soc. 45, (1939). 
               736-739.
%D A003313 Downey, Peter; Leong, Benton; Sethi, Ravi; Computing sequences with addition 
               chains. SIAM J. Comput. 10 (1981), 638-646.
%D A003313 Elia, M. and Neri, F.; A note on addition chains and some related conjectures, 
               in Sequences (Naples/Positano, 1988), pp. 166-181, Springer, New 
               York, 1990.
%D A003313 P. Erdos, Remarks on number theory. III. On addition chains. Acta Arith. 
               6 1960 77-81.
%D A003313 A. Flammenkamp, Drei Beitraege zur diskreten Mathematik: Additionsketten, 
               No-Three-in-Line-Problem, Sociable Numbers, Diplomarbeit, Bielefeld 
               1991.
%D A003313 Gashkov, S. B. and Kochergin, V. V.; 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 Gioia, A. A.; Subba Rao, M. V.; Sugunamma, M.; The Scholz-Brauer problem 
               in addition chains. Duke Math. J. 29 1962 481-487.
%D A003313 Gioia, A. A. and Subbarao, M. V., 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 Graham, R. L.; Yao, A. C. C.; Yao, F. F., Addition chains with multiplicative 
               cost. Discrete Math. 23 (1978), 115-119.
%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 McCarthy, D. P., Effect of improved multiplication efficiency on exponentiation 
               algorithms derived from addition chains. Math. Comp. 46 (1986), 603-608.
%D A003313 Olivos, Jorge, On vectorial addition chains. J. Algorithms 2 (1981), 
               13-21.
%D A003313 Schoenhage, Arnold, A lower bound for the length of addition chains. 
               Theor. Comput. Sci. 1 (1975), 1-12.
%D A003313 Thurber, Edward G. The Scholz-Brauer problem on addition chains. Pacific 
               J. Math. 49 (1973), 229-242.
%D A003313 Thurber, Edward G. On addition chains ... and lower bounds for c(r). 
               Duke Math. J. 40 (1973), 907-913.
%D A003313 Thurber, Edward G., Addition chains and solutions of l(2n)=l(n) and l(2^n-1)=n+l(n)-1. 
               Discrete Math. 16 (1976), 279-289.
%D A003313 Thurber, Edward G., Addition chains-an erratic sequence. Discrete Math. 
               122 (1993), 287-305.
%D A003313 Thurber, Edward G., Efficient generation of minimal length addition chains. 
               SIAM J. Comput. 28 (1999), 1247-1263.
%D A003313 W. R. Utz, A note on the Scholz-Brauer problem in addition chains. Proc. 
               Amer. Math. Soc. 4, (1953). 462-463.
%D A003313 Vegh, Emanuel, A note on addition chains. J. Combinatorial Theory Ser. 
               A 19 (1975), 117-118.
%D A003313 Whyburn, C. T., A note on addition chains. Proc. Amer. Math. Soc. 16 
               1965 1134.
%H A003313 D. W. Wilson, <a href="b003313.txt">Table of n, a(n) for n = 1..10001</
               a>
%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, Zuerich 1996. 
               See p. 61.
%H A003313 Achim Flammenkamp, <a href="http://wwwhomes.uni-bielefeld.de/achim/addition_chain.html">
               Shortest addition chains</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 Alec Mihailovs, <a href="a003313b.txt">Notes on using Flammenkamp's tables</
               a>
%H A003313 Hugo Pfoertner, <a href="a003313.txt">Addition chains</a>
%H A003313 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               AdditionChain.html">Link to a section of The World of Mathematics 
               (1).</a>
%H A003313 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               ScholzConjecture.html">Link to a section of The World of Mathematics 
               (2).</a>
%H A003313 Kari Ragnarsson, Bridget Eileen Tenner, <a href="http://arxiv.org/abs/
               0802.2550">Obtainable Sizes of Topologies on Finite Sets</a>, Oct 
               6, 2008, to appear in Journal of Combinatorial Theory, Series A. 
               [From Jonathan Vos Post (jvospost3(AT)gmail.com), Oct 08 2008]
%F A003313 It seems that, for n>1, ln(n) < a(n) < (5/2)*ln(n); lim n ->infinity 
               sum(k=1, n, a(k))/(n*ln(n)-n) = C = 1.8(4).... - Benoit Cloitre Oct 
               30 2002
%F A003313 a(n^k) <= k * a(n). - Max Alekseyev (maxale(AT)gmail.com), Jul 22, 2005
%F A003313 For all n => 2, a(n) =< (4/3)floor(log_2 n) + 2. [From Jonathan Vos Post 
               (jvospost3(AT)gmail.com), Oct 08 2008]
%e A003313 a(n) is the depth of n in the following tree (see Knuth, Vol. 2, Sect. 
               4.6.3, Fig. 14):
%e A003313 ................1
%e A003313 ................|
%e A003313 ................2
%e A003313 .............../..\
%e A003313 ............../.....\
%e A003313 ............3..........4
%e A003313 ........./....\.........\
%e A003313 ......../......\.........\
%e A003313 .....5..........6..........8
%e A003313 ..../..\........|......../...\
%e A003313 ..7....10......12......9.......16
%e A003313 ./..../..\..../..\..../.\...../..\
%e A003313 14...11..20..15..24..13..17..18..32
%Y A003313 Cf. A003064, A003065, A005766.
%Y A003313 Sequence in context: A122953 A128998 A137813 this_sequence A117497 A117498 
               A064097
%Y A003313 Adjacent sequences: A003310 A003311 A003312 this_sequence A003314 A003315 
               A003316
%K A003313 nonn,nice
%O A003313 1,3
%A A003313 N. J. A. Sloane (njas(AT)research.att.com).
%E A003313 More terms from Jud McCranie (j.mccranie(AT)comcast.net), Nov 01 2001
%E A003313 Replaced arxiv URL by non-cached version - R. J. Mathar (mathar(AT)strw.leidenuniv.nl), 
               Oct 07 2009