A003313 -id:A003313 - cp's OEIS frontend

A122352 Knuth's power tree represented by parent node number.

0, 1, 2, 2, 3, 3, 5, 4, 6, 5, 10, 6, 10, 7, 10, 8, 16, 9, 14, 10, 14, 11, 13, 12, 15, 13, 18, 14, 28, 15, 28, 16, 17, 17, 21, 18, 36, 19, 26, 20, 40, 21, 40, 22, 30, 23, 42, 24, 48, 25, 48, 26, 52, 27, 44, 28, 38, 29, 31, 30, 56, 31, 42, 32, 64, 33, 66, 34, 46, 35, 57, 36, 37, 37

Offset: 1

Franklin T. Adams-Watters, Aug 30 2006

nonn

This method of representing the power tree is suggested by exercise 10 in Section 4.6.3 page 481 TAOCP Vol. 2.

			The power tree sequence for 54 is 1,2,3,6,9,18,27,54, so a(54) = 27.

D. E. Knuth, The Art of Computer Programming Third Edition. Vol. 2, Seminumerical Algorithms. Chapter 4.6.3 Evaluation of Powers, Page 464. Addison-Wesley, Reading, MA, 1997.

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Hugo Pfoertner, Addition chains

Cf. A114622.

A265690 Cardinality of shortest addition chain for n.

Original entry on oeis.org

1, 2, 3, 3, 4, 4, 5, 4, 5, 5, 6, 5, 6, 6, 6, 5, 6, 6, 7, 6, 7, 7, 7, 6, 7, 7, 7, 7, 8, 7, 8, 6, 7, 7, 8, 7, 8, 8, 8, 7, 8, 8, 8, 8, 8, 8, 9, 7, 8, 8, 8, 8, 9, 8, 9, 8, 9, 9, 9, 8, 9, 9, 9, 7, 8, 8, 9, 8, 9, 9, 10, 8, 9, 9, 9, 9, 9, 9, 10, 8, 9, 9, 9, 9, 9, 9, 10, 9, 10, 9, 10, 9, 10, 10, 10, 8, 9, 9, 9, 9

Offset: 1

Franklin T. Adams-Watters, Dec 13 2015

nonn

The cardinality of an addition chain is the number of terms in it, including the initial 1; hence it is one more than the length of the chain (A003313).

Wikipedia, Addition chain

Cf. A003313 (much more information and links), A265691, A265692.

a(n) = A003313(n) + 1.

A266082 Length of shortest Fibonacci addition chain for n.

Original entry on oeis.org

0, 1, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 7, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 8, 8, 9, 9, 9, 9, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 10, 9, 9, 9, 9, 10, 10, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 9

Offset: 1

Franklin T. Adams-Watters, Dec 21 2015

By Fibonacci addition chain is meant an addition chain where no doubling steps are allowed. The fastest growing chains of this type are the Fibonacci numbers, as compared with the powers of 2 for an unrestricted addition chain. The chain is considered to start with 2 1's, so that the 2 can be generated.
These chains provide ways to generate the product x^n in some abstract system where for some reason squaring is expensive, perhaps because multiplying involves temporarily changing the input values. There are no obvious actual practical applications.
Based on that, one might want to allow copying a value in the chain as an elementary operation. However, this is not necessary: one can just repeat the sum used to generate the number. Further, even that is not necessary to generate a minimal length chain. If k is in the chain, the only possible use for another copy of it is to generate 2k. But if k  was generated as i+j, one can replace k, k, ..., 2k with k, ..., k+i, ..., k+i+j, and the last is equal to 2k.
One can generate a power tree for these chains, but it is less useful than for general addition chains. Generating it the same way fails to find a minimal chain for 12. One does somewhat better reversing the standard procedure and genating the larger values first; this fails to be minimal first for 25.

			The only Fibonacci addition chains of length 2 are 1, 1, 2, 3 and 1, 1, 2, 2. Neither generates 4. However, 4 can be appended to either of them to get a chain of length 3. Hence a(4) = 3.
a(30) = 7 because there is no shorter chain than 1, 1, 2, 3, 5, 8, 11, 19, 30.

Lars Blomberg, Table of n, a(n) for n = 1..233

Cf. A003313, A000045.

Corrected a(30) by Lars Blomberg, Mar 16 2017

A383330 Triangle read by rows: T(n,k) is the length of a shortest vectorial addition chain for (n,k), 0 <= k <= n.

Original entry on oeis.org

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

Offset: 0

Pontus von Brömssen, Apr 26 2025

Starting with (1,0) and (0,1), each pair of the chain must be equal to the sum of two preceding pairs. The length of the chain is defined to be the number of pairs in the chain, excluding (1,0) and (0,1).
Also, T(n,k) is the least number of multiplications needed to obtain x^n*y^k, starting with x and y.
T(0,0) = 0 by convention.

			Triangle begins:
  n\k| 0  1  2  3  4  5  6  7  8  9 10
  ---+--------------------------------
   0 | 0
   1 | 0  1
   2 | 1  2  2
   3 | 2  3  3  3
   4 | 2  3  3  4  3
   5 | 3  4  4  4  4  4
   6 | 3  4  4  4  4  5  4
   7 | 4  5  5  5  5  5  5  5
   8 | 3  4  4  5  4  5  5  6  4
   9 | 4  5  5  5  5  5  5  6  5  5
  10 | 4  5  5  5  5  5  5  6  5  6  5
A shortest addition chain for (11,7) is [(1,0), (0,1),] (1,1), (2,1), (4,2), (5,3), (10,6), (11,7) of length T(11,7) = 6.

Richard Bellman, Problem 5125, Advanced problems and solutions, The American Mathematical Monthly 70 (1963), p. 765.
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. A003313 (column k=0, excluding T(0,0)), A265690 (column k=1 and main diagonal; apparently also column k=2), A383331, A383332.

A383335 Length of shortest addition-multiplication-exponentiation chain for n.

Original entry on oeis.org

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

Offset: 1

Pontus von Brömssen, Apr 27 2025

nonn

An addition-multiplication-exponentiation chain for n is a finite sequence of numbers, starting with 1 and ending with n, in which each element except 1 equals x+y, x*y, or x^y for two preceding elements x and y (not necessarily distinct). The length of the chain is the number of elements in the chain, excluding 1.

			a(248) = 5 because the shortest addition-multiplication-exponentiation chain for 248 has length 5: (1, 2, 3, 5, 243, 248).

Pontus von Brömssen, Table of n, a(n) for n = 1..10000

Cf. A003313, A128998, A230697, A383336, A383337.

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

A075100 Number of words of length strictly between 1 and n that are needed on the way to computing all words of length n in the free monoid with two generators.

Original entry on oeis.org

0, 0, 3, 4, 10, 11

Offset: 1

Colin Mallows, Aug 31 2002

I believe a(2n) = a(n) + 2^n. I think a(7) = 28.

Benoit Jubin (Jan 24 2009) suggests replacing "monoid" in the definition by "semigroup" and remarks that it makes sense to introduce a new sequence that includes words of length 1 in the count.

			a(3) = 3 because we need only xx, xy, yy to generate each of xxx, xxy, xyx, yxx, xyy, yxy, yyx, yyy.

Cf. A075099, A003313, A124677.

Edited by Andrey Zabolotskiy, Nov 08 2024

A104892 Smallest number whose shortest Lucas chain is of length n.

Original entry on oeis.org

2, 3, 5, 7, 11, 17, 23, 37, 53, 83, 127, 197, 331, 461, 739, 1123, 1801, 2903, 4463, 6947, 10973, 17539, 26627, 43103, 67079, 109639, 160649, 271829, 432199, 665789, 1080491, 1666943, 2668909, 4182169, 6786257, 10612027, 17010151, 26901547, 42105257, 67208321, 105414851, 169631897, 265359847, 423344501, 672662981, 1065233261, 1653387299, 2680042177, 4243717559, 6698246557

Offset: 1

N. J. A. Sloane, May 23 2008

nonn

Daniel Bleichenbacher, Efficiency and Security of Cryptosystems based on Number Theory, PhD Thesis, Diss. ETH No. 11404, Zürich 1996. See p. 69.
Neill Clift, Lucas/Differential Addition Chains.
Wikipedia, Lucas chain.
Index to sequences related to the complexity of n

Cf. A105096, A105195, A003313.

a(30) onwards from Neill M. Clift, Oct 19 2024

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.

A256653 Numbers k such that the factor method (A064097) for computing the k-th power has fewer multiplications than Knuth's power tree method (A114622).

Original entry on oeis.org

19879, 39758, 43277, 60749, 79516, 86554, 121498, 136199, 159032, 173069, 173108, 183929, 242996, 252941, 272398, 318064, 346138, 346216, 362861, 367757, 367858, 453281, 456017, 485992, 505882, 544796, 561727, 579193, 603167, 636128, 637969, 692276, 692432, 725722, 735514, 735709, 735716, 772193, 906562, 912034, 931297, 963649, 971984, 1011764, 1051727

Offset: 1

Max Alekseyev at the suggestion of Hugo Pfoertner, Apr 06 2015

nonn

Hugo Pfoertner, Addition chains.
V. Zhuravlev, P. Samovol, Faster than the fastest, or can one beat the binary algorithm, Kvant 2 (2013), 7-15. (in Russian)

Cf. A003313, A064097, A114622, A230528.

cp's OEIS Frontend

A122352 Knuth's power tree represented by parent node number.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A265690 Cardinality of shortest addition chain for n.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A266082 Length of shortest Fibonacci addition chain for n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A383330 Triangle read by rows: T(n,k) is the length of a shortest vectorial addition chain for (n,k), 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A383335 Length of shortest addition-multiplication-exponentiation chain for n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A075100 Number of words of length strictly between 1 and n that are needed on the way to computing all words of length n in the free monoid with two generators.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A104892 Smallest number whose shortest Lucas chain is of length n.

Views

Author

Keywords

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Crossrefs

A256653 Numbers k such that the factor method (A064097) for computing the k-th power has fewer multiplications than Knuth's power tree method (A114622).

Views

Author

Keywords

Links