1,3

Equivalently, minimal number of multiplications required to compute n-th power.

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]

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

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.

Bergeron, F.; Berstel, J.; Brlek, S.; Duboc, C.; Addition chains using continued fractions. J. Algorithms 10 (1989), 403-412.

D. Bleichenbacher, Efficiency and Security of Cryptosystems based on Number Theory, Dissertation, ETH Zurich 1996.

D. Bleichenbacher and A. Flammenkamp, An Efficient Algorithm for Computing Shortest Addition Chains, Preprint, 1997.

Brauer, Alfred, On addition chains. Bull. Amer. Math. Soc. 45, (1939). 736-739.

Downey, Peter; Leong, Benton; Sethi, Ravi; Computing sequences with addition chains. SIAM J. Comput. 10 (1981), 638-646.

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.

P. Erdos, Remarks on number theory. III. On addition chains. Acta Arith. 6 1960 77-81.

A. Flammenkamp, Drei Beitraege zur diskreten Mathematik: Additionsketten, No-Three-in-Line-Problem, Sociable Numbers, Diplomarbeit, Bielefeld 1991.

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.

Gioia, A. A.; Subba Rao, M. V.; Sugunamma, M.; The Scholz-Brauer problem in addition chains. Duke Math. J. 29 1962 481-487.

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.

Graham, R. L.; Yao, A. C. C.; Yao, F. F., Addition chains with multiplicative cost. Discrete Math. 23 (1978), 115-119.

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.

McCarthy, D. P., Effect of improved multiplication efficiency on exponentiation algorithms derived from addition chains. Math. Comp. 46 (1986), 603-608.

Olivos, Jorge, On vectorial addition chains. J. Algorithms 2 (1981), 13-21.

Schoenhage, Arnold, A lower bound for the length of addition chains. Theor. Comput. Sci. 1 (1975), 1-12.

Thurber, Edward G. The Scholz-Brauer problem on addition chains. Pacific J. Math. 49 (1973), 229-242.

Thurber, Edward G. On addition chains ... and lower bounds for c(r). Duke Math. J. 40 (1973), 907-913.

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.

Thurber, Edward G., Addition chains-an erratic sequence. Discrete Math. 122 (1993), 287-305.

Thurber, Edward G., Efficient generation of minimal length addition chains. SIAM J. Comput. 28 (1999), 1247-1263.

W. R. Utz, A note on the Scholz-Brauer problem in addition chains. Proc. Amer. Math. Soc. 4, (1953). 462-463.

Vegh, Emanuel, A note on addition chains. J. Combinatorial Theory Ser. A 19 (1975), 117-118.

Whyburn, C. T., A note on addition chains. Proc. Amer. Math. Soc. 16 1965 1134.

D. W. Wilson, Table of n, a(n) for n = 1..10001

Daniel Bleichenbacher, Efficiency and Security of Cryptosystems based on Number Theory. PhD Thesis, Diss. ETH No. 11404, Zuerich 1996. See p. 61.

Achim Flammenkamp, Shortest addition chains

D. E. Knuth, See the achain-all program

Alec Mihailovs, Notes on using Flammenkamp's tables

Hugo Pfoertner, Addition chains

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (1).

Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics (2).

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]

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

a(n^k) <= k * a(n). - Max Alekseyev (maxale(AT)gmail.com), Jul 22, 2005

For all n => 2, a(n) =< (4/3)floor(log_2 n) + 2. [From Jonathan Vos Post (jvospost3(AT)gmail.com), Oct 08 2008]

a(n) is the depth of n in the following tree (see Knuth, Vol. 2, Sect. 4.6.3, Fig. 14):

................1

................|

................2

.............../..\

............../.....\

............3..........4

........./....\.........\

......../......\.........\

.....5..........6..........8

..../..\........|......../...\

..7....10......12......9.......16

./..../..\..../..\..../.\...../..\

14...11..20..15..24..13..17..18..32

Cf. A003064, A003065, A005766.

Sequence in context: A122953 A128998 A137813 this_sequence A117497 A117498 A064097

Adjacent sequences: A003310 A003311 A003312 this_sequence A003314 A003315 A003316

nonn,nice

N. J. A. Sloane (njas(AT)research.att.com).

More terms from Jud McCranie (j.mccranie(AT)comcast.net), Nov 01 2001

Replaced arxiv URL by non-cached version - R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Oct 07 2009