A384480 Square array read by antidiagonals: T(n,k) is the length of a shortest addition-composition chain for n*x+k, starting with 1 and x; n, k >= 0.

0, 0, 0, 1, 1, 1, 2, 2, 2, 2, 2, 3, 2, 3, 2, 3, 3, 3, 3, 3, 3, 3, 4, 3, 3, 3, 4, 3, 4, 4, 4, 4, 3, 4, 4, 4, 3, 5, 4, 4, 3, 4, 4, 5, 3, 4, 4, 4, 4, 4, 4, 4, 5, 4, 3, 4, 5, 4, 5, 3, 4, 4, 5, 4, 4, 4, 5, 5, 5, 5, 4, 4, 4, 5, 4, 5, 5, 4, 4, 5, 5, 5, 4, 4, 4, 5, 4, 4, 5, 5, 4

Offset: 0

Author

Pontus von Brömssen, Jun 02 2025

Keywords

• nonn
• tabl

Comments

An addition-composition chain for the affine function f is a finite sequence of affine functions, starting with 1, x and ending with f, in which each element except 1 and x equals g(x)+h(x) or g(h(x)) for two preceding, not necessarily distinct, elements g(x) and h(x) in the chain. The length of the chain is the number of elements in the chain, excluding 1 and x. Such chains exist only for functions of the form f(x) = n*x+k, where n and k are nonnegative integers, not both 0.

T(0,0) = 0 by convention.

Equivalently, the chains can be defined on pairs (s,t) of nonnegative integers (corresponding to the function f(x) = s*x+t) with the operations (s,t)+(u,v) = (s+t,u+v) (addition) and (s,t)o(u,v) = (s*u,s*v+t) (composition).

Examples

			Array begins:
  n\k| 0  1  2  3  4  5  6  7  8  9 10 11 12
  ---+--------------------------------------
   0 | 0  0  1  2  2  3  3  4  3  4  4  5  4
   1 | 0  1  2  3  3  4  4  5  4  5  5  5  5
   2 | 1  2  2  3  3  4  4  4  4  5  5  5  5
   3 | 2  3  3  3  4  4  4  5  5  5  5  5  5
   4 | 2  3  3  3  3  4  3  4  4  4  4  5  4
   5 | 3  4  4  4  4  4  4  4  5  5  5  5  5
   6 | 3  4  4  4  4  4  4  5  4  4  5  5  5
   7 | 4  5  5  5  5  5  5  5  5  5  5  6  6
   8 | 3  4  4  4  4  4  4  4  4  5  4  5  4
   9 | 3  4  5  4  4  5  5  5  4  5  5  5  4
  10 | 4  5  5  5  5  5  5  5  5  5  5  6  5
  11 | 4  5  6  5  5  5  6  6  6  5  5  6  6
  12 | 4  5  5  5  5  5  5  5  5  5  5  5  5
For (n,k) = (4,6), the unique shortest chain for 4*x+6 is (1, x,) x+1, 2*x+2, 4*x+6 of length T(4,6) = 3. The last term of the chain is the composition of 2*x+2 with itself.
For (n,k) = (6,4), a shortest chain for 6*x+4 is (1, x,) x+1, 2*x+2, 3*x+2, 6*x+4 of length T(6,4) = 4. This chain uses only additions.
		

Crossrefs

Cf. A383330 (addition only), A384481, A384482, A384483 (row 0).

Formula

T(n,k) <= T(n,k-1) + 1.

T(n,k) <= T(n-1,k) + 1.