login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003313 Length of shortest addition chain for n.
(Formerly M0255)
52
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 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. - Jonathan Vos Post, Oct 08 2008

REFERENCES

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. Bleichenbacher and A. Flammenkamp, An Efficient Algorithm for Computing Shortest Addition Chains, Preprint, 1997.

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.

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. 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. 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.

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

LINKS

D. W. Wilson and Antoine Mathys, Table of n, a(n) for n = 1..100000 (10001 terms from D. W. Wilson)

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

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

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

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

Christian Elsholtz et al, Upper bound on length of addition chain, Math Overflow, Sep 18 2015.

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

Achim Flammenkamp, Shortest addition chains

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

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

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

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

Alec Mihailovs, Notes on using Flammenkamp's tables

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

Hugo Pfoertner, Addition chains

Kari Ragnarsson, Bridget Eileen Tenner, Obtainable Sizes of Topologies on Finite Sets, Oct 06 2008, Journal of Combinatorial Theory, Series A 117 (2010) 138-151.

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

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

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

Edward G. Thurber, Addition chains and solutions of l(2n)=l(n) and l(2^n-1)=n+l(n)-1, Discrete Math., Vol. 16 (1976), 279-289.

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

Edward G. Thurber, 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.

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

Eric Weisstein's World of Mathematics, Addition Chain

Eric Weisstein's World of Mathematics, Scholz Conjecture

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

Index to sequences related to the complexity of n

FORMULA

It seems that, for n>1, log(n) < a(n) < (5/2)*log(n); lim n ->infinity sum(k=1, n, a(k))/(n*log(n)-n) = C = 1.8(4).... - Benoit Cloitre, Oct 30 2002

a(n*m) <= a(n)+a(m). In particular, a(n^k) <= k * a(n). - Max Alekseyev, Jul 22 2005

For all n >= 2, a(n) <= (4/3)floor(log_2 n) + 2. - Jonathan Vos Post, Oct 08 2008

For all n >= 2, a(n) <= 1.620412 log_2(n), see Segal-Halevi et al. link. - Erel Segal-Halevi, Sep 15 2015

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

Cf. A003064, A003065, A005766, A230528.

Sequence in context: A259103 A128998 A137813 * A117497 A117498 A064097

Adjacent sequences:  A003310 A003311 A003312 * A003314 A003315 A003316

KEYWORD

nonn,nice,look

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Jud McCranie, Nov 01 2001

arXiv URL replaced with non-cached version by R. J. Mathar, Oct 07 2009

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified July 23 05:54 EDT 2016. Contains 274947 sequences.