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

2, 4, 14, 62, 350, 2517, 22918, 259325

Offset: 0

Author

Pontus von Brömssen, Jun 01 2025

Keywords

• nonn
• more

Comments

An addition-multiplication 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) or q(x)*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

			a(0) = 2 because 1 and x are considered to have chains of length 0.
a(1) = 4 because the 4 polynomials 2, x+1, 2*x, and x^2 have chains of length 1.
a(2) = 14 because the 14 polynomials 3, 4, x+2, 2*x+1, 2*x+2, 3*x, 4*x, x^2+1, x^2+x, x^2+2*x+1, 2*x^2, 4*x^2, x^3, and x^4 have chains of length 2.
		

Crossrefs

Cf. A382928, A383002, A383331 (addition only), A384383 (addition, multiplication, and composition), A384482 (addition and composition).