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

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

Offset: 1

Author

Pontus von Brömssen, Jun 01 2025

Keywords

• nonn

Comments

See A384383 for the definition of addition-multiplication-composition chains. The number n is identified with the constant polynomial p(x) = n.

Examples

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

Crossrefs

Cf. A230697 (addition and multiplication), A384383, A384385, A384386, A384483 (addition and composition).

Formula

a(n) <= A230697(n).

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