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

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

Author

Pontus von Brömssen, Apr 26 2025

Keywords

• nonn
• tabl

Comments

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.

Examples

			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.
		

Links

• 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.

Crossrefs

Cf. A003313 (column k=0, excluding T(0,0)), A265690 (column k=1 and main diagonal; apparently also column k=2), A383331, A383332.