善莫大焉什么意思

Question

In this challenge, you are given a polynomial \$p(x)\$, and you need to find a polynomial \$q(x)\$ whose roots are exactly the squares of the roots of \$p(x)\$ (counted with multiplicity). In other words, if \$p(x) = \prod_{i=1}^n (x - r_i)\$, then \$q(x) = \prod_{i=1}^n (x - r_i^2)\$.

For example, if \$p(x) = x^3 - 3 x^2 + 4 = (x + 1)(x - 2)^2\$, then the roots of \$p(x)\$ are \$-1, 2, 2\$. So the roots of \$q(x)\$ are \$1, 4, 4\$, and thus \$q(x) = (x - 1)(x - 4)^2 = x^3 - 9 x^2 + 24 x - 16\$. Of course, \$2 (x - 1)(x - 4)^2 = 2 x^3 - 18 x^2 + 48 x - 32\$ is also a valid answer, as it has the same roots with the same multiplicities.

The input \$p(x)\$ is guaranteed to be a non-constant polynomial with integer coefficients, but some roots may be complex or repeated. Your output \$q(x)\$ does not need to have integer coefficients, but there is always a valid answer with integer coefficients.

You may input and output the polynomials in any reasonable format. For example, the polynomial \$x^4-4x^3+5x^2-2x\$ may be represented as:

• a list of coefficients, in descending order: [1,-4,5,-2,0];
• a list of coefficients, in ascending order:[0,-2,5,-4,1];
• a string representation of the polynomial, with a chosen variable, e.g., x: "x^4-4*x^3+5*x^2-2*x";
• a built-in polynomial object, e.g., x^4-4*x^3+5*x^2-2*x in PARI/GP.

When you take input as a list of coefficients, the leading coefficient is guaranteed to be nonzero.

Representing a polynomial by its roots is not a reasonable format for this challenge, as it would make the task trivial.

This is code-golf, so the shortest code in bytes wins.

Test cases

The output is not unique. Your output may be a non-zero multiple of the expected output.

Here the polynomials are represented as lists of coefficients in decreasing order.

[1, 1] -> [1, -1]                           # x + 1 => x - 1
[1, 1, 1] -> [1, 1, 1]                      # x^2 + x + 1 => x^2 + x + 1
[1, -3, 4] -> [1, -1, 16]                   # x^2 - 3x + 4 => x^2 - x + 16
[1, 2, 3, 4] -> [1, 2, -7, -16]             # x^3 + 2x^2 + 3x + 4 => x^3 + 2x^2 - 7x - 16
[1, 2, 1, 0] -> [1, -2, 1, 0]               # x^3 + 2x^2 + x => x^3 - 2x^2 + x
[1, -4, 5, -2, 0] -> [1, -6, 9, -4, 0]      # x^4 - 4x^3 + 5x^2 - 2x => x^4 - 6x^3 + 9x^2 - 4x
[1, 2, 3, 4, 5] -> [1, 2, 3, 14, 25]        # x^4 + 2x^3 + 3x^2 + 4x + 5 => x^4 + 2x^3 + 3x^2 + 14x + 25

Answer 1

Wolfram Language (Mathematica), 21 bytes

Resultant[#,x^2-a,x]&

Try it online!

Answer 2

Jelly, 5 bytes

?r2??

A monadic Link that accepts and yields coefficients in descending order.

Try it online!

How?

Builtins...

?r2?? - Link: list of numbers, Coefficients
?r    - roots of {Coefficients}
  2   - square {those}
   ?? - polynomial with roots {that}

Answer 3

Charcoal, 30 24 bytes

ＩＥθΣＥθΣＥθ∧??κ?μξ×Ｘ±1ξ×λν

Try it online! Link is to verbose version of code. I/O is a list in ascending order of exponent. Explanation: Directly calculates a polynomial whose roots are the squares of the given polynomial. Works even when the original roots do not have a closed form. Edit: Saved 6 bytes by using @Albert.Lang's optimisation to calculate the sign of each term.

  θ                         Input array
 Ｅ                          Map over values
     θ                      Input array
    Ｅ                       Map over values
        θ                   Input array
       Ｅ                    Map over values
            κ               Outer index
           ?                Doubled
          ?                 Equals
              μ             Inner index
             ?              Plus
               ξ            Innermost index
         ∧                  Logical And
                   1        Literal integer `1`
                  ±         Negated
                 Ｘ          Raised to power
                    ξ       Innermost index
                ×           Multiplied by
                      λ     Inner value
                     ×      Multiplied by
                       ν    Innermost value
      Σ                     Take the sum
   Σ                        Take the sum
Ｉ                           Cast to string
                            Implicitly print

Answer 4

Python + NumPy, 35 bytes

lambda p:p*0+[*p*p(p*0-[1,0])][::2]

Attempt This Online!

Takes and returns instances of numpy.poly1d.

How?

Multplies the given polynomial p(x) with its "mirror" q(x):=p(-x). For each root r of p, q has a root -r and the product has a quadratic factor (x²-r²). Dropping every other coefficient (they are all 0 anyways) in effect substitutes x² by some new variable z, so the resulting polynomial has the correct roots.

The p*0 terms are type coercion starters.

Previous Python + NumPy, 36 bytes

lambda p:p*0+(p*p(p*0-[1,0])).c[::2]

Attempt This Online!

Previous Python + NumPy, 63 bytes

lambda p:P((p*p(-P([1,0]))).c[::2])
from numpy import*
P=poly1d

Attempt This Online!

(Boring) Python + NumPy, 45 bytes

lambda p:poly(roots(p)**2)
from numpy import*

Attempt This Online!

Answer 5

Haskell, 64 bytes

h?(a:b:t)=2*h*b:h?t++[0]
_?l=[0]
f(h:t)=h^2:zipWith(-)(h?t)(f t)

Try it online!

No built-in algebra, just list manipulation. Given \$p\$, we're looking for \$q\$ with

$$ q(x^2) = p(x)p(-x)$$

If we express \$p(x) = h + x p'(x)\$, then we can recurse as

$$p(x)p(-x) = h^2+x^2 \left( 2h \frac{p'(x)-p'(-x)}{2x} - p'(x)p'(-x)\right)$$

So, the first term of \$q(x^2)\$ is \$h^2\$, and the remaining terms are the expression after \$x^2\$. The term \$\frac{p'(x)-p'(-x)}{2x}\$ deletes every other coefficient from \$p'(x)\$. From it, we subtract \$ p'(x)p'(-x)\$, which is the recursive evaluation of our main function on \$p'(x)\$.

If we may stretch polynomial representation to an infinite list trailing with zeroes, we can just write:

Haskell, 51 bytes

h?(a:b:t)=2*h*b:h?t
f(h:t)=h^2:zipWith(-)(h?t)(f t)

Try it online!

Answer 6

JavaScript (ES7), 60 bytes

This is a port of Neil's answer.

a=>a.map((_,k)=>a.reduce((t,x,i)=>t+(-1)**i*x*~~a[k*2-i],0))

Try it online!