Given an integral polynomial of degree strictly greater than one, completely decompose it into a composition of integral polynomials of degree strictly greater than one.
- An integral polynomial is a polynomial with only integers as coefficients.
- Given two polynomials
qthe composition is defined by
- The decomposition of an integral polynomial
pis a finite ordered sequence of integral polynomials
deg qi > 1for all
1 ≤ i ≤ nand
p(x) = q1(q2(...qn(x)...)), and all
qiare not further decomposable. The decomposition is not necessarily unique.
- You can use e.g. lists of coefficients or built in polynomial types as input and output.
- Note that many builtins for this task actually decompose the polynomials over a given field and not necessarily integers, while this challenge requires a decomposition integer polynomials. (Some integer polynomials might admit decomposition into integer polynomials as well as decomposition that contain rational polynomials.)
x^2 + 1 [x^2 + 1] (all polynomials of degree 2 or less are not decomposable) x^6 - 6x^5 + 15x^4 - 20x^3 + 15x^2 - 6 x - 1 [x^3 - 2, x^2 - 2x + 1] x^4 - 8x^3 + 18x^2 - 8x + 2 [x^2 + 1, x^2 - 4x + 1] x^6 + x^2 + 1 [x^3 + x + 1, x^2] x^6 [x^2, x^3] x^8 + 4x^6 + 6x^4 + 4x^2 + 4 = (x^2 + 1)^4 + 3 [x^2 + 3, x^2, x^2 + 1] x^6 + 6x^4 + x^3 + 9x^2 + 3x - 5 [x^2 + x - 5, x^3 + 3*x], [x^2 + 5*x + 1, x^3 + 3*x - 2]
Use Maxima for generating examples: Try it online!