A384483 Length of shortest addition-composition chain for n, starting with 1 and x.

0, 1, 2, 2, 3, 3, 4, 3, 4, 4, 5, 4, 5, 5, 5, 4, 5, 5, 6, 5, 5, 5, 6, 5, 5, 5, 5, 6, 6, 6, 5, 5, 6, 6, 6, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 5, 6, 6, 6, 6, 6, 7, 6, 6, 6, 6, 6, 6, 7, 6, 7, 6, 5, 6, 6, 6, 6, 6, 7

Offset: 1

Author

Pontus von Brömssen, Jun 02 2025

Keywords

• nonn

Comments

See A384480 for the definition of addition-composition chains. The number n is identified with the constant function f(x) = n.

Examples

			The smallest n for which a(n) < A003313(n) is n = 21. The length of a shortest addition chain for 21 is A003313(21) = 6, but there are addition-composition chains of length 5, for example (1, x,) x+1, 2*x+2, 3*x+3, 6, 21. 6 and 21 are the compositions of 3*x+3 with 1 and 6, respectively.
		

Crossrefs

Row 0 of A384480 for columns k >= 1.

Cf. A003313 (addition only), A230697 (addition and multiplication), A384384 (addition, multiplication, and composition), A384484, A384485.

Formula

a(n) <= A003313(n).

a(n) <= a(n-1) + 1.