A079300 -id:A079300 - cp's OEIS frontend

A003313 Length of shortest addition chain for n.

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

Offset: 1

N. J. A. Sloane

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

			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.

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. Bleichenbacher and A. Flammenkamp, An Efficient Algorithm for Computing Shortest Addition Chains, Preprint, 1997.
A. Flammenkamp, Drei Beitraege zur diskreten Mathematik: Additionsketten, No-Three-in-Line-Problem, Sociable Numbers, Diplomarbeit, Bielefeld 1991.
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.
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. 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.
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.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

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, and C. Duboc, Addition chains using continued fractions, J. Algorithms 10 (1989), 403-412.
Wawrzyniec Bieniawski, Piotr Masierak, Andrzej Tomski, and Szymon Łukaszyk, Assembly Theory - Formalizing Assembly Spaces and Discovering Patterns and Bounds, Preprints.org (2025).
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.
John M. Campbell, A binary version of the Mahler-Popken complexity function, arXiv:2403.20073 [math.NT], 2024. See pp. 3-4. See also Integers (2024) Vol. 24, Art. No. A94. See pp. 3, 10.
Peter Downey, Benton Leong, and Ravi Sethi, Computing sequences with addition chains SIAM J. Comput. 10 (1981), 638-646.
M. Elia and F. Neri, A note on addition chains and some related conjectures, (Naples/Positano, 1988), pp. 166-181 of R. M. Capocelli, ed., Sequences, Springer-Verlag, NY 1990.
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.
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, Problems and solutions of the Fourth International Students' Olympiad in Cryptography NSUCRYPTO, arXiv:1806.02059 [cs.CR], 2018.
R. L. Graham, A. C.-C. Yao, and F. F. Yao, Addition chains with multiplicative cost Discrete Math. 23 (1978), 115-119.
D. Knuth, Letter to N. J. A. Sloane, date unknown
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 and Bridget Eileen Tenner, Obtainable Sizes of Topologies on Finite Sets, arXiv:0802.2550 [math.CO], 2008-2009; 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

Cf. A003064, A003065, A005766, A014701, A079300, A230528.

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
From Achim Flammenkamp, Oct 26 2016: (Start)
a(n) <= 9/log_2(71) log_2(n), for all n.
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)
a(n) <= A014701(n). - Charles R Greathouse IV, Jan 03 2018
From Szymon Lukaszyk, Apr 05 2024: (Start)
For n = 2^s, a(n)=s;
for n = 2^s + 2^m, m in [0..s-1] (A048645), a(n)=s+1;
for n = 2^s + 3*2^m, m in [0..s-2] (A072823), a(n)=s+2;
for n = 2^s + 7*2^(s-3), s>2 (A072823), a(n)=s+2.(End)

More terms from Jud McCranie, Nov 01 2001

A079301 a(n) = number of shortest addition chains for n that are Brauer chains.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 5, 1, 3, 4, 15, 3, 9, 14, 4, 1, 2, 7, 31, 6, 26, 40, 4, 4, 13, 22, 5, 23, 114, 12, 64, 1, 2, 4, 43, 12, 33, 87, 18, 8, 20, 78, 4, 69, 14, 8, 183, 5, 11, 34, 4, 35, 171, 16, 139, 32, 148, 308, 33, 24, 76, 201, 80, 1, 2, 4, 23, 6, 26, 134, 1014

Offset: 1

David W. Wilson, Feb 09 2003

nonn

In a general addition chain, each element > 1 is a sum of two previous elements. In a Brauer chain, each element > 1 is a sum of the immediately previous element and another previous element.

			All five of the shortest addition chains for 7 are Brauer chains: (1,2,3,4,7), (1,2,3,5,7), (1,2,3,6,7), (1,2,4,5,7), (1,2,4,6,7). Hence a(7) = 5.
13 has ten shortest addition chains: (1,2,3,5,8,13), (1,2,3,5,10,13), (1,2,3,6,7,13), (1,2,3,6,12,13), (1,2,4,5,9,13), (1,2,4,6,7,13), (1,2,4,6,12,13), (1,2,4,8,9,13), (1,2,4,8,12,13), and (1,2,4,5,8,13). Of these, all but the last are Brauer chains. Hence a(13) = 9.
12509 has 28 shortest addition chains, none of which are Brauer chains. Hence a(12509) = 0.

Glen Whitney, Table of n, a(n) for n = 1..18286 (Terms 1..1024 from D. W. Wilson)
Eric Weisstein's World of Mathematics, Brauer Chain
Glen Whitney, C program to compute A079300, also generates this sequence.

Definition disambiguated by Glen Whitney, Nov 06 2021

A079302 a(n) = number of shortest addition chains for n that are non-Brauer chains.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 2, 0, 3, 0, 0, 0, 1, 2, 0, 0, 18, 0, 13, 0, 0, 0, 0, 0, 6, 5, 2, 0, 3, 6, 0, 0, 0, 0, 37, 0, 1, 2, 0, 3, 34, 0, 17, 0, 25, 44, 4, 0, 15, 32, 7, 0, 0, 0, 0, 0, 3, 0, 244, 0, 7, 13, 2, 8, 0, 6, 129, 0, 3, 6

Offset: 1

David W. Wilson, Feb 09 2003

nonn

In a general addition chain, each element > 1 is a sum of two previous elements (the two may be the same element). In a Brauer chain, each element > 1 is a sum of the immediately previous element and another previous element. Conversely, a non-Brauer chain has at least one element that is the sum of two elements earlier than the preceding one.

			7 has five shortest addition chains: (1,2,3,4,7), (1,2,3,5,7), (1,2,3,6,7), (1,2,4,5,7), and (1,2,4,6,7). All of these are Brauer chains. Hence a(7) = 0.
13 has ten shortest addition chains: (1,2,3,5,8,13), (1,2,3,5,10,13), (1,2,3,6,7,13), (1,2,3,6,12,13), (1,2,4,5,9,13), (1,2,4,6,7,13), (1,2,4,6,12,13), (1,2,4,8,9,13), (1,2,4,8,12,13), and (1,2,4,5,8,13). Of these, only the last is non-Brauer. Hence a(13) = 1.
12509 has 28 shortest addition chains, all of which happen to be non-Brauer (in fact, it is the smallest natural number for which all shortest addition chains are non-Brauer). Hence a(12509) = A079300(12509) = 28.

Glen Whitney, Table of n, a(n) for n = 1..18286 (Terms 1..1024 from D. W. Wilson)
Eric Weisstein's World of Mathematics, Brauer Chain.
Glen Whitney, C program to compute A079300, also generates this sequence.

Cf. A079300, the total number of minimal addition chains.

Definition disambiguated by Glen Whitney, Nov 06 2021

A008057 Smallest sum of an addition chain for 2n+1.

Original entry on oeis.org

0, 5, 10, 16, 20, 27, 31, 35, 40, 47, 51, 56, 60, 65, 74, 78, 80, 86, 92, 96, 102, 106, 110, 120, 121, 125, 134, 137, 142, 148, 153, 156, 160, 167, 171, 182, 184, 185, 192, 201, 200, 206, 210, 219, 227, 231, 233, 237, 241, 245

Offset: 0

N. J. A. Sloane, Aug 07 2003

			The smallest chain for 5 is 2, 3, 5 with sum a(2) = 2+3+5 = 10.
The smallest chain for 7 is 2, 3, 4, 7 with sum a(3) = 2+3+4+7 = 16.

H. Zantema, Minimizing sums of addition chains, RUU-CS-89-15 (1989).
H. Zantema, Minimizing sums of addition chains, J. Algorithms 12 (1991) 281-307.
Index to sequences related to the complexity of n

Cf. A003313, A079300, A003065, A005766, A376449.

step(V)=my(U=List(),v); for(i=1,#V, v=V[i]; for(i=1,#v, for(j=i,#v, if(v[i]+v[j]>v[#v], listput(U, concat(v, v[i]+v[j])))))); vecsort(Vec(U),,8)
sm(v)=sum(i=2,#v,v[i])
a(n)=if(n<2,return(5*n)); n=2*n+1; my(V=[[1,2]],U,t); while(#(U=select(v->v[#v]==n,V))==0, V=select(v->v[#v]<=n,step(V))); t=vecmin(apply(sm,U)); while(#V, V=step(select(v->sm(v)Charles R Greathouse IV, Jul 17 2013

a(n) = A376449(2*n+1) + 2*n. - Pontus von Brömssen, Apr 22 2025

a(30)-a(46) from Sean A. Irvine, Mar 08 2018

a(47)-a(49) (using A376449 b-file) from Pontus von Brömssen, Apr 22 2025

A118386 Numbers k such that k has a record number of distinct shortest addition chains.

Original entry on oeis.org

1, 5, 7, 11, 19, 22, 29, 47, 58, 71, 127, 142, 191, 446, 508, 607, 758, 1087, 1214

Offset: 1

David W. Wilson, Apr 26 2006

Computed by Neill M. Clift. Verified up to a(17) by David W. Wilson. Indices of record values of A079300.

Cf. A003313, A079300.

A186435 Number of evaluation schemes for x^n achieving the minimal number of multiplications.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 6, 1, 3, 4, 19, 3, 10, 16, 4, 1, 2, 7, 37, 6, 31, 48, 4, 4, 14, 24, 5, 26, 152, 12, 80, 1, 2, 4, 51, 12, 39, 100, 20, 8, 23, 90, 4, 81, 14, 8, 242, 5, 12, 36, 4, 38, 215, 16, 172, 36, 190, 395, 40, 24

Offset: 1

Laurent Thevenoux and Christophe Mouilleron, Feb 23 2011

nonn

			For n=7, we can evaluate x^7 using only 4 multiplications in 6 ways:
x^2 = x * x ; x^3 = x   * x^2 ; x^4 = x   * x^3 ; x^7 = x^3 * x^4
x^2 = x * x ; x^3 = x   * x^2 ; x^4 = x^2 * x^2 ; x^7 = x^3 * x^4
x^2 = x * x ; x^3 = x   * x^2 ; x^5 = x^2 * x^3 ; x^7 = x^2 * x^5
x^2 = x * x ; x^3 = x   * x^2 ; x^6 = x^3 * x^3 ; x^7 = x   * x^6
x^2 = x * x ; x^4 = x^2 * x^2 ; x^5 = x   * x^4 ; x^7 = x^2 * x^5
x^2 = x * x ; x^4 = x^2 * x^2 ; x^6 = x^2 * x^4 ; x^7 = x   * x^6

See A003313 for the minimal number of multiplications to evaluate x^n.
See A001190 for the total number of evaluation schemes for x^n (regardless of the number of effective multiplications).
A079300 gives the number of minimal chains (= sequences of powers of x) ending at x^n. This is actually a bit less than the number of evaluation schemes since two schemes may produce the same chain, like the first and second schemes in the example above, where the corresponding chain is (x^2, x^3, x^4, x^7).

A086833 Minimum number of different addends occurring in any shortest addition chain of Brauer type for a given n, or 0 if n has no shortest addition chain of Brauer type.

Original entry on oeis.org

1, 1, 1, 2, 2, 2, 2, 3, 2, 3, 3, 3, 3, 3, 3, 4, 4, 3, 3, 4, 3, 4, 5, 4, 4, 4, 3, 4, 4, 4, 4, 5, 5, 5, 4, 4, 4, 4, 4, 5, 5, 4, 6, 5, 4, 6, 4, 5, 5, 5, 5, 5, 5, 4, 4, 5, 4, 5, 5, 5, 5, 5, 4, 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 5, 7, 5, 5, 6, 4, 6, 7, 5, 6, 7, 5, 6, 6, 5, 5, 7, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5

Offset: 1

Tatsuru Murai, Aug 08 2003

nonn

n = 12509 is the first n for which a(n) = 0 because it is the smallest number that has no shortest addition chain of Brauer type. - Hugo Pfoertner, Jun 10 2006 [Edited by Pontus von Brömssen, Apr 25 2025]

			a(23)=5 because 23=1+1+2+1+4+9+5 is the shortest addition chain for 23.
For n=9 there are A079301(9)=3 different shortest addition chains, all of Brauer type:
[1 2 3 6 9] -> 9=1+1+1+3+3 -> 2 different addends {1,3}
[1 2 4 5 9] -> 9=1+1+2+1+4 -> 3 different addends {1,2,4}
[1 2 4 8 9] -> 9=1+1+2+4+1 -> 3 different addends {1,2,4}
The minimum number of different addends is 2, therefore a(9)=2.

Giovanni Resta, Tables of Shortest Addition Chains, computed by David W. Wilson.
Index to sequences related to the complexity of n

Cf. A003064, A003065, A003313, A005766, A008057, A008928, A008933, A079300, A079300, A079301, A349044.

a(n) = 0 if and only if n is in A349044. - Pontus von Brömssen, Apr 25 2025

Edited by Hugo Pfoertner, Jun 10 2006

Escape clause added by Pontus von Brömssen, Apr 25 2025

cp's OEIS Frontend

A118387 Record values in A079300 (number of shortest addition chains of n).

Views

Author

Keywords

Comments

References

Crossrefs

Formula

A003313 Length of shortest addition chain for n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A079301 a(n) = number of shortest addition chains for n that are Brauer chains.

Views

Author

Keywords

Comments

Examples

Links

Extensions

A079302 a(n) = number of shortest addition chains for n that are non-Brauer chains.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A008057 Smallest sum of an addition chain for 2n+1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A118386 Numbers k such that k has a record number of distinct shortest addition chains.

Views

Author

Keywords

Comments

Crossrefs

A186435 Number of evaluation schemes for x^n achieving the minimal number of multiplications.

Views

Author

Keywords

Examples

Crossrefs

A086833 Minimum number of different addends occurring in any shortest addition chain of Brauer type for a given n, or 0 if n has no shortest addition chain of Brauer type.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions