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,1

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.

Links

Table of n, a(n) for n=0..7.

Example

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).

Sequence in context: A027740 A132880 A019537 * A046911 A089127 A132852

Adjacent sequences: A384379 A384380 A384381 * A384383 A384384 A384385

Keyword

nonn,more

Author

Pontus von Brömssen, Jun 01 2025

Status

approved