A383334 -id:A383334 - cp's OEIS frontend

A383332 Smallest positive weight of a pair of nonnegative integers with a shortest vectorial addition chain of length n.

1, 2, 3, 4, 6, 8, 12, 20, 29, 44, 70, 104

Offset: 0

Pontus von Brömssen, Apr 26 2025

See A383330 for details.

The weight of a pair is the sum of its elements.

			   n | a(n) | pairs (x,y) with x <= y, x+y = a(n), and shortest chain length n
  ---+------+-----------------------------------------------------------------
   0 |   1  | (0,1)
   1 |   2  | (0,2), (1,1)
   2 |   3  | (0,3), (1,2)
   3 |   4  | (1,3)
   4 |   6  | (1,5)
   5 |   8  | (1,7)
   6 |  12  | (1,11)
   7 |  20  | (1,19), (3,17)
   8 |  29  | (6,23)
   9 |  44  | (7,37)
  10 |  70  | (11,59)
  11 | 104  | (15,89)

Row 2 of A383334.

Cf. A003064, A383330, A383331.

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

A383332 Smallest positive weight of a pair of nonnegative integers with a shortest vectorial addition chain of length n.

Views

Author

Keywords

Comments

Examples

Crossrefs