14
\$\begingroup\$

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 , 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
Improve this question
\$\endgroup\$

7 Answers 7

Reset to default
8
\$\begingroup\$

Wolfram Language (Mathematica), 21 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
7
\$\begingroup\$

Jelly, 5 bytes

Ær²Æṛ

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

Try it online!

How?

Builtins...

Ær²Æṛ - Link: list of numbers, Coefficients Ær - roots of {Coefficients} ² - square {those} Æṛ - polynomial with roots {that}
Improve this answer
\$\endgroup\$
7
\$\begingroup\$

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 (x2-r2). Dropping every other coefficient (they are all 0 anyways) in effect substitutes x2 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!

Improve this answer
\$\endgroup\$
5
\$\begingroup\$

Charcoal, 30 24 bytes

ＩＥθΣＥθΣＥθ∧⁼⊗κ⁺μξ×Ｘ±¹ξ×λν

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 ¹ 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
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Huh, you already found the (-1)**i simplification... I had to port it from @Albert.Lang's answer. \$\endgroup\$ Commented Aug 4 at 21:44
  • \$\begingroup\$ @Neil Ah yes, forgot to mention that it was a port of your future answer. :p (I'm not doing (-1)**i anymore but the idea remains the same.) \$\endgroup\$ Commented Aug 5 at 7:21
2
\$\begingroup\$

Husk, 12 bytes

mΣĊ2∂SṪ*z*İ_

Try it online! This uses the standard procedure of calculating -P(x)*P(-x) and dropping the odd-indexed terms. The output coefficients are negated due to the unusual definition of İ_, which is an infinite list of -(-1)^n instead of (-1)^n.

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.