A384383 Number of polynomials with a shortest addition-multiplication-composition chain of length n, starting with 1 and x.

2, 4, 14, 73, 586, 7250

Offset: 0

Author

Pontus von Brömssen, Jun 01 2025

Keywords

• nonn
• more

Comments

An addition-multiplication-composition chain for the polynomial p(x) is a finite sequence of polynomials, starting with 1, x and ending with p(x), in which each element except 1 and x equals q(x)+r(x), q(x)*r(x), or q(r(x)) for two preceding, not necessarily distinct, elements q(x) and r(x) in the chain. The length of the chain is the number of elements in the chain, excluding 1 and x.

Examples

			An example of a polynomial for which composition is necessary to obtain the shortest chain is 9*x, with the chain (1, x,) 2*x, 3*x, 9*x. (9*x is the composition of 3*x with itself.) So 9*x is one of the 11 polynomials counted by a(3) but not by A384382(3).
		

Crossrefs

Cf. A382928, A383331 (addition only), A384382 (addition and multiplication), A384386, A384482 (addition and composition).