A383332 -id:A383332 - cp's OEIS frontend

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.

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.

A384481 Smallest value of f(1) for a function f(x) = b*x+c with nonnegative integer coefficients and a shortest addition-composition chain of length n, starting with 1 and x.

Original entry on oeis.org

1, 2, 3, 4, 6, 8, 13, 24, 46, 98

Offset: 0

Pontus von Brömssen, Jun 02 2025

See A384480 for details.

			  n | functions b*x+c with b+c = a(n) and shortest chain of length n
  --+---------------------------------------------------------------
  0 | 1, x
  1 | 2, x+1, 2*x
  2 | 3, x+2, 2*x+1, 3*x
  3 | 3+x, x+3
  4 | 5+x, x+5
  5 | 7+x, x+7
  6 | 11*x+2
  7 | 23*x+1
  8 | 7*x+39, 43*x+3
  9 | 11*x+87

Cf. A383332 (addition only), A384480, A384482, A384484.

A383334 Square array read by antidiagonals: T(n,k) is the smallest positive weight of an n-tuple of nonnegative integers with a shortest vectorial addition chain of length k; n >= 1, k >= 0.

Original entry on oeis.org

1, 2, 1, 3, 2, 1, 5, 3, 2, 1, 7, 4, 3, 2, 1, 11, 6, 4, 3, 2, 1, 19, 8, 5, 4, 3, 2, 1, 29, 12, 7, 5, 4, 3, 2, 1, 47, 20, 9, 6, 5, 4, 3, 2, 1, 71, 29, 13, 8, 6, 5, 4, 3, 2, 1, 127, 44, 20, 10, 7, 6, 5, 4, 3, 2, 1, 191, 70, 30, 14, 9, 7, 6, 5, 4, 3, 2, 1

Offset: 1

Pontus von Brömssen, Apr 26 2025

See A383333 for details.

T(n,k) is the smallest positive degree of a monomial 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  8
  ---+--------------------------
  1  | 1  2  3  5  7 11 19 29 47
  2  | 1  2  3  4  6  8 12 20 29
  3  | 1  2  3  4  5  7  9 13 20
  4  | 1  2  3  4  5  6  8 10 14
  5  | 1  2  3  4  5  6  7  9 11
The smallest positive weight of a triple of nonnegative integers with a shortest addition chain of length 8 is T(3,8) = 20. Up to permutations, (3,4,13) is the only such triple, with a shortest addition chain [(1,0,0), (0,1,0), (0,0,1),] (0,0,2), (0,0,4), (0,1,4), (1,1,4), (2,2,8), (3,3,12), (3,3,13), (3,4,13).

Cf. A383333.

Rows: A003064 (n=1), A383332 (n=2).

cp's OEIS Frontend

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

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

A384481 Smallest value of f(1) for a function f(x) = b*x+c with nonnegative integer coefficients and a shortest addition-composition chain of length n, starting with 1 and x.

Views

Author

Keywords

Comments

Examples

Crossrefs

A383334 Square array read by antidiagonals: T(n,k) is the smallest positive weight of an n-tuple of nonnegative integers with a shortest vectorial addition chain of length k; n >= 1, k >= 0.

Views

Author

Keywords

Comments

Examples

Crossrefs