OFFSET
0,5
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.
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.
EXAMPLE
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.
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Pontus von Brömssen, Apr 26 2025
STATUS
approved
