A003065 -id:A003065 - 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

A003064 a(n) = smallest number with shortest addition chain of length n.

Original entry on oeis.org

1, 2, 3, 5, 7, 11, 19, 29, 47, 71, 127, 191, 379, 607, 1087, 1903, 3583, 6271, 11231, 18287, 34303, 65131, 110591, 196591, 357887, 685951, 1176431, 2211837, 4169527, 7624319, 14143037, 25450463, 46444543, 89209343, 155691199, 298695487, 550040063, 994660991

Offset: 0

N. J. A. Sloane and Don Knuth

An addition chain of length n for a number a is a sequence 1 = a_0, a_1,..., a_n = a such that for each i>0, a_i is the sum of two (not necessarily distinct) elements of the sequence. - Glen Whitney, Nov 09 2021
The largest number with an addition chain of length n is 2^n. This chain is of course shortest for 2^n. - Franklin T. Adams-Watters, Jan 20 2016
The step from a_{i-1} to a_i is called "small" if a_i is less than the smallest power of two greater than a_{i-1}. The sequence b(n) of the smallest number which requires n small steps in an addition chain is a subsequence of this sequence, starting a(0), a(2), a(4), a(7), a(10), a(15), a(21), a(28), a(37), a(46),... - Glen Whitney, Nov 09 2021

			a(7) = 29 because 29 is the smallest number with a shortest addition chain requiring 7 additions. An example of a shortest addition chain for 29 is (1 2 3 4 7 11 18 29).

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 2, p. 458; Vol. 2, 3rd. ed., p. 477.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
See A003313 for a much more extensive list of references and links.

Glen Whitney, Table of n, a(n) for n = 0..46 (Terms 0..41 from R. J. Mathar)
Daniel Bleichenbacher, Efficiency and Security of Cryptosystems based on Number Theory, PhD Thesis, Diss. ETH No. 11404, Zürich 1996. See p. 60.
Swee Hong Chan and Igor Pak, Computational complexity of counting coincidences, arXiv:2308.10214 [math.CO], 2023. See p. 10.
M. Elia and F. Neri, A note on addition chains and some related conjectures, pp. 166-181 of R. M. Capocelli, ed., Sequences, Springer-Verlag, NY 1990. The smallest number with an addition chain of length n is denoted c(n) in this paper.
Achim Flammenkamp, Shortest addition chains
D. Knuth, Letter to N. J. A. Sloane, date unknown
Index to sequences related to the complexity of n

This is the "smallest inverse" of A003313. Cf. A003065.

Cf. A075530, A115617 [Smallest number for which Knuth's power tree method produces an addition chain of length n].

New terms from Achim Flammenkamp, Math. Diplomarbeit, Univ. Bielefeld, 1991; and from Daniel Bleichenbacher (bleichen(AT)inf.ethz.ch)
a(25)-a(27) from the 3rd. ed. of Knuth vol. 2, sent by David Moulton, Jun 24 2003
a(28)-a(30) from Achim Flammenkamp's web site, Feb 01 2005
a(31) computed Dec 15 2005 by Neill M. Clift. - Hugo Pfoertner, Jan 29 2006
a(32) from Neill M. Clift, Jun 15 2007
a(33)-a(34) from Neill M. Clift, May 21 2008
b-file up to a(41) extracted from Achim Flammenkamp's web site. - R. J. Mathar, May 14 2013
b-file updated to a(46) from Achim Flammenkamp's web site. - Glen Whitney, Nov 09 2021

A216999 Number of integers obtainable from 1 in n steps using addition, multiplication, and subtraction.

Original entry on oeis.org

1, 3, 6, 13, 38, 153, 867, 6930, 75986, 1109442, 20693262, 477815647

Offset: 0

Stan Wagon, Sep 22 2012

A straight-line program is a sequence that starts at 1 and has each entry obtained from two preceding entries by addition, multiplication, or subtraction. S(n) is the set of integers obtainable at any point in a straight-line program using n steps. Thus S(0) = {1}, S(1) = {0,1,2}, S(2) = {-1,0,1,2,3,4}; the sequence here is the cardinality of S(n).

Peter Borwein and Joe Hobart, The extraordinary power of division in straight line programs, American Mathematical Monthly 119:7 (2012), pp. 584-592.
Michael Shub and Steve Smale, On the intractability of Hilbert's Nullstellensatz and an algebraic version of "NP = P", Duke Mathematical Journal 81:1 (1995), pp. 47-54.

Cf. A003065, A141414, A173419, A288849, A288850.

extend[p_] :=  Module[{q = Tuples[p, {2}], new},
  new = Flatten[Table[{Total[t], Subtract @@ t, Times @@ t}, {t, q}]];
  Union[ Sort /@  DeleteCases[ Table[If[! MemberQ[p, n], Append[p, n]], {n, new}], Null]]] ;
P[0] = {{1}};
P[n_] := P[n] = DeleteDuplicates[Flatten[extend /@ P[n - 1], 1]];
S[n_] := DeleteDuplicates[Flatten[P[n]]];
Length /@ S /@ Range[6]

a(9)-a(11) (Michael Collier verified independently the 1109442, 20693262 values) by Gil Dogon, Sep 27 2013

A217032 Minimum number of steps to reach n! starting from 1 and using the operations of multiplication, addition, or subtraction.

Original entry on oeis.org

0, 1, 3, 4, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 12, 12, 13, 13

Offset: 1

Stan Wagon, Sep 24 2012

A straight-line program is a sequence that starts at 1 and has each entry obtained from two preceding entries by addition, multiplication, or subtraction. This sequence lists the smallest number of steps needed to reach n!. A 10-step solution for 12 is {1, 2, 4, 6, 24, 30, 720, 900, 924, 518400, 12!}, found by Stan Wagon; John Guilford found all such, and proved that 10 is minimal for 12! - edited by Stan Wagon, Nov 07 2012
This sequence describes the difficulty of computing the factorial in Valiant's model. If it is of polynomial growth -- that is, there exists some c such that a(n) < (log n)^c for all n -- then the factorial is said to be easy to compute, and consequently "the Hilbert Nullstellensatz is intractable, and consequently the algebraic version of 'NP != P' is true" (Shub & Smale). - Charles R Greathouse IV, Sep 24 2012
During Al Zimmermann's contest (see link), Ed Mertensotto generated all sequences of 12 steps and found no better solutions. Hence a(13)-a(17) are optimal. Solutions of 13 steps were found for a(18) and a(19) during the contest. Hence, they are optimal too. - Dmitry Kamenetsky, Apr 22 2013

			The entry for 9! is 8 because of the straight-line program {1, 2, 3, 9, 8, 72, 70, 7!, 9!}; subtraction is essential to getting 9! in 8 steps. The entry for 10! is 9 because of the straight-line program {1, 2, 3, 5, 7, 12, 144, 6!, 7!, 10!}, which does not use subtraction.

Peter Borwein and Joe Hobart, The extraordinary power of division in straight line programs, American Mathematical Monthly 119:7 (2012), pp. 584-592.
P. Koiran, Valiant's model and the cost of computing integers, Comput. Complex. 13 (2004), pp. 131-146. [DOI]
Ed Mertensotto, post about enumerating all sequences of 12 steps [broken link]
Ed Mertensotto, Tomas G. Rokicki, Gil Dogon, Search, digest of 25 messages in AlZimmermannsProgrammingContests Yahoo group, Mar 19 - Apr 23, 2013.
Michael Shub and Steve Smale, On the intractability of Hilbert's Nullstellensatz and an algebraic version of "NP = P", Duke Mathematical Journal 81:1 (1995), pp. 47-54. [DOI]
Stan Wagon, Macalester Problem of the Week 1153
Al Zimmermann, Al Zimmermann's Programming Contests: Factorials
Index to sequences related to the complexity of n

Cf. A216999, A217031, A173419, A003065, A141414.

a(n) = A173419(n!) >= A217031(n). - Charles R Greathouse IV, Sep 24 2012

a(12) from Charles R Greathouse IV, Oct 04 2012

a(13)-a(19) from Ed Mertensotto, Mar 20 2013

A383002 Number of integers with a shortest addition-multiplication chain of length n.

Original entry on oeis.org

1, 1, 2, 5, 16, 63, 331, 2239, 19909, 225615, 3167570

Offset: 0

Pontus von Brömssen, Apr 12 2025

a(n) is the number of occurrences of n in A230697.

Cf. A003065, A230697, A383001.

A383331 Number of pairs of nonnegative integers, not both equal to 0, with a shortest vectorial addition chain of length n.

Original entry on oeis.org

2, 3, 7, 16, 37, 91, 229, 585, 1528, 4034, 10862

Offset: 0

Pontus von Brömssen, Apr 26 2025

See A383330 for details.

Row 2 of A383333.

Cf. A003065, A383330, A383332.

A384485 Number of integers with a shortest addition-composition chain of length n, starting with 1 and x, i.e., number of integers k with A384483(k) = n.

Original entry on oeis.org

1, 1, 2, 3, 5, 20, 104, 700, 6779, 95596

Offset: 0

Pontus von Brömssen, Jun 02 2025

See A384480 and A384483 for details.

Cf. A003065 (addition only), A383002 (addition and multiplication), A384386 (addition, multiplication, and composition), A384480, A384482, A384483, A384484.

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

A383143 Number of positive integers with a shortest addition-subtraction chain of length n.

Original entry on oeis.org

1, 1, 2, 3, 5, 9, 16, 28, 49, 88, 156, 280, 499, 904, 1639, 2986, 5442, 9936, 18134

Offset: 0

Jinyuan Wang, Apr 17 2025

			a(6) = 16 because the number of occurrences of 6 in A128998 is 16. These numbers are 19, 21, 22, 23, 25, 26, 27, 28, 30, 31, 33, 34, 36, 40, 48, 64.

Neill Clift, Addition Subtraction Chains.
Index to sequences related to the complexity of n

Cf. A003065, A128998, A383002, A383142.

a(n) >= A003065(n).

A383333 Square array read by antidiagonals: T(n,k) is the number of n-tuples of nonnegative integers, not all equal to 0, with a shortest vectorial addition chain of length k; n >= 1, k >= 0.

Original entry on oeis.org

1, 1, 2, 2, 3, 3, 3, 7, 6, 4, 5, 16, 16, 10, 5, 9, 37, 46, 30, 15, 6, 15, 91, 134, 101, 50, 21, 7, 26, 229, 411, 349, 190, 77, 28, 8, 44, 585, 1319, 1264, 751, 323, 112, 36, 9, 78, 1528, 4368, 4817, 3106, 1426, 511, 156, 45, 10, 136, 4034, 14925, 19131, 13532, 6586, 2478, 766, 210, 55, 11

Offset: 1

Pontus von Brömssen, Apr 26 2025

The n unit tuples (1, 0, ..., 0), ... (0, ..., 0, 1) are given for free, so T(n,0) = n.
Starting with the n unit tuples, each tuple of a chain must be equal to the sum of two preceding tuples. The length of the chain is defined to be the number of tuples in the chain, excluding the unit tuples.
Also, T(n,k) is the number of non-constant monomials x_1^e_1*...*x_n^e_n that requires k multiplications, given x_1, ..., x_n.

			Array begins:
  n\k| 0  1  2   3    4    5     6      7
  ---+-----------------------------------
  1  | 1  1  2   3    5    9    15     26
  2  | 2  3  7  16   37   91   229    585
  3  | 3  6 16  46  134  411  1319   4368
  4  | 4 10 30 101  349 1264  4817  19131
  5  | 5 15 50 190  751 3106 13532  61748
  6  | 6 21 77 323 1426 6586 32035 163594
There are 12 triples of nondecreasing nonnegative integers with a shortest addition chain of length 3. Counting also the permutations of these, we get T(3,3) = 46:
  (0, 0, 5):  3
  (0, 0, 6):  3
  (0, 0, 8):  3
  (0, 1, 3):  6
  (0, 1, 4):  6
  (0, 2, 3):  6
  (0, 2, 4):  6
  (0, 3, 3):  3
  (0, 4, 4):  3
  (1, 1, 2):  3
  (1, 2, 2):  3
  (2, 2, 2):  1
      Total: 46

Jorge Olivos, On vectorial addition chains, Journal of Algorithms 2 (1981), 13-21.
E. G. Straus, Partial solution to problem 5125: Addition chains of vectors, Problems and solutions, The American Mathematical Monthly 71 (1964), 806-808.
Edward G. Thurber and Neill M. Clift, Addition chains, vector chains, and efficient computation, Discrete Mathematics 344 (2021), 112200.
Wikipedia, Vectorial addition chain.

Cf. A383334.
Rows: A003065 (n=1), A383331 (n=2).
Columns: A000027 (k=0), A000217 (k=1), A005581 (k=2).

cp's OEIS Frontend

A003313 Length of shortest addition chain for n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A003064 a(n) = smallest number with shortest addition chain of length n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A216999 Number of integers obtainable from 1 in n steps using addition, multiplication, and subtraction.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A217032 Minimum number of steps to reach n! starting from 1 and using the operations of multiplication, addition, or subtraction.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A383002 Number of integers with a shortest addition-multiplication chain of length n.

Views

Author

Keywords

Comments

Crossrefs

A383331 Number of pairs of nonnegative integers, not both equal to 0, with a shortest vectorial addition chain of length n.

Views

Author

Keywords

Comments

Crossrefs

A384485 Number of integers with a shortest addition-composition chain of length n, starting with 1 and x, i.e., number of integers k with A384483(k) = n.

Views

Author

Keywords

Comments

Crossrefs

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A383143 Number of positive integers with a shortest addition-subtraction chain of length n.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A383333 Square array read by antidiagonals: T(n,k) is the number of n-tuples of nonnegative integers, not all equal to 0, with a shortest vectorial addition chain of length k; n >= 1, k >= 0.