Search: id:A003313 Results 1-1 of 1 results found. %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, Table of n, a(n) for n = 1..10001 %H A003313 Daniel Bleichenbacher, Efficiency and Security of Cryptosystems based on Number Theory. PhD Thesis, Diss. ETH No. 11404, Zuerich 1996. See p. 61. %H A003313 Achim Flammenkamp, Shortest addition chains %H A003313 D. E. Knuth, See the achain-all program %H A003313 Alec Mihailovs, Notes on using Flammenkamp's tables %H A003313 Hugo Pfoertner, Addition chains %H A003313 Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (1). %H A003313 Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (2). %H A003313 Kari Ragnarsson, Bridget Eileen Tenner, Obtainable Sizes of Topologies on Finite Sets, 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 Search completed in 0.002 seconds