11
\$\begingroup\$

Given a nonzero polynomial with integer coefficients and roots that are on the imaginary and on the real line such that if a is a root then so is -a, return another polynomial with the roots rotated by 90 degrees.

Details

The polynomial can be given in any reasonable format, e.g. as a list of coefficients. The symmetry condition that a is a root if and only if -a is a root too enforces the rotated polynomial to have real integer coefficients as well.

Examples

In the following the polynomials are given as a list of coefficient of the monomials in descending degree. (i.e. the constant comes last) The polynomial x^2-1 has roots {1,-1}. Rotating them by 90° means multiplying by i (the imaginary unit), so the output polynomial should have the roots {i,-i}, which is x^2 + 1.

Input / Output
[1 0 10 0 -127 0 -460 0 576]  [1 0 -10 0 -127 0 460 0 576]
[1 0 -4 0] [1 0 4 0]
[1] [1]
Improve this question
\$\endgroup\$
8
  • \$\begingroup\$ May I take in the degree of the polynomial as well as the polynomial \$\endgroup\$
    – Rohan Jhunjhunwala
    May 14, 2017 at 15:19
  • \$\begingroup\$ Yes I think that is acceptable. \$\endgroup\$
    – flawr
    May 14, 2017 at 16:01
  • \$\begingroup\$ All your examples use monic polynomials. Can we assume the input polynomial will be monic? Does the output polynomial have to be monic? \$\endgroup\$
    – Dennis
    May 14, 2017 at 16:05
  • \$\begingroup\$ No it can also have other leading coefficients than 1, and the output is also just defined up to a integral multiple. \$\endgroup\$
    – flawr
    May 14, 2017 at 16:07
  • \$\begingroup\$ It seems the format doesn't have to be a list of coefficients. How far do the reasonable formats go? Can my format be a string expression in the indeterminate x, so that my submission can string-replace x with (i*x)? Can my format a function that evaluates the polynomial, so that my submission is to compose it with the function x -> i*x? \$\endgroup\$
    – xnor
    May 14, 2017 at 19:48

10 Answers 10

Reset to default
12
\$\begingroup\$

Mathematica, 10 Bytes

Pure function which takes a function of x and substitutes in ix.

#/.x->I*x&

Alternative with only 7 bytes but not quite sure if it counts. Pure function which takes in a pure function and returns a function of x.

#[I*x]&
Improve this answer
\$\endgroup\$
4
  • 5
    \$\begingroup\$ And you didn't even need any builtins! \$\endgroup\$
    – Neil
    May 14, 2017 at 16:34
  • \$\begingroup\$ I'm pretty sure a pure function polynomial is a "reasonable format" (like it was here) It uses # as the variable and has a & at the end. \$\endgroup\$
    – JungHwan Min
    May 14, 2017 at 17:14
  • \$\begingroup\$ I would upvote this twice if I could \$\endgroup\$
    – Greg Martin
    May 14, 2017 at 17:23
  • \$\begingroup\$ My only concern about the second answer was the mismatch between input (a pure function) and output (a function of x). \$\endgroup\$
    – Ian Miller
    May 15, 2017 at 0:16
7
\$\begingroup\$

Jelly, 5 bytes

Jı*Ċ×

Try it online!

How it works

Multiplies the first element by 1, the third element by -1, etc.

Jı*Ċ×  argument: z
J      [1,2,...,len(z)]
 ı     i (the imaginary unit)
  *    to the power of (each element)
   Ċ   imaginary part
    ×  multiply by input (vectorize)

Proof of algorithm

Let the polynomial be f(x).

Since we are guaranteed that if x is a root then so is -x, so f must be even, meaning that its coefficient for the odd powers must be 0.

Now, rotating the roots by 90° is essentially f(ix).

Expanding then comparing coefficients proves the algorithm.

Improve this answer
\$\endgroup\$
10
  • \$\begingroup\$ So, we need not touch the 2,4th,6th, 8th etc? \$\endgroup\$
    – Rohan Jhunjhunwala
    May 14, 2017 at 15:19
  • 2
    \$\begingroup\$ Those are zero anyway. \$\endgroup\$
    – flawr
    May 14, 2017 at 15:21
  • \$\begingroup\$ Your trick with ı*Ċ is very nice, you should explain it :) \$\endgroup\$
    – Leo
    May 14, 2017 at 19:01
  • \$\begingroup\$ @Leo It's essentially a straightforward implementation though... \$\endgroup\$
    – Leaky Nun
    May 15, 2017 at 1:06
  • \$\begingroup\$ The logic here is not quite right, because you can instead have all coefficients for even powers be 0. \$\endgroup\$
    – Ørjan Johansen
    May 15, 2017 at 1:52
5
\$\begingroup\$

JavaScript (ES6), 25 bytes

a=>a.map((e,i)=>i%4?-e:e)

The original polynomial has solutions of the form x = ±a where a lies on the real or imaginary line. Except when a = 0 (in which case x is a factor of the polynomial), this means that x² - a² is a factor of the polynomial (which means alternate terms are always zero). Now when we rotate the roots, the factor changes to x² + a². Since all the factors change at the same time, the third term of the polynomial, which is the sum of all the -a² terms, changes sign, the fifth term, which is the sum of products of pairs of -a² terms, keeps the same sign, etc. alternating every other term.

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Octave, 27 bytes

@(x)round(poly(roots(x)*j))

Try it online!

This directly applies the definition: compute roots, multiply by j, convert back from roots to polynomial. A final rounding is necessary because of floating-point numerical errors.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Python 3, 42 bytes

f=lambda x,s=1:x and[0,x[0]*s]+f(x[2:],-s)

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

S.I.L.O.S, 71 66 bytes

readIO
b=i
lbla
readIO
d=c
d&2
i=i*(1-d)
printInt i
b-1
c+1
if b a

Try it online!

I have no clue what wizardry @Leaky Nun did here to save 5 bytes.

Took me a second to figure out, but The second bit of C will alternate like we want. Therefore @Leaky Nun exploited this to save the bits we need.

Improve this answer
\$\endgroup\$
1
0
\$\begingroup\$

TI-Basic, 20 bytes

seq(real(i^X/i)Ans(X),X,1,dim(Ans

If stored in prgmA, run with:

{1, 0, 3, 0, 1}:prgmA

seq( just had to be the one* command that doesn't support complex numbers. :)

*: Exaggeration

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Casio-Basic, 8 bytes

n|x=𝑖x

Unnamed function, using Ian Miller's Mathematica approach. The imaginary 𝑖 from the Math2 keyboard needs to be used (counts as 2 bytes, char code 769), and the polynomial should be entered as an equation of x.

7 bytes for the code, 1 byte to specify n as a parameter.

Explanation: Takes the equation n, then simply replaces all instances of x with 𝑖x.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Pari/GP, 16 bytes

p->x=I*x;eval(p)

Try it online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Stax, 5 bytes

Æ[]▐↨

Run and debug online!

Port of the Jelly answer.

Uses ASCII representation to explain:

mih|1*
m         Map each element with rest of program, print mapped results on individual lines
 i        Current 0-based loop index
  h       Floor(i/2)
   |1     (-1)^(i/2)
     *    Multiply with current element

If there can be leading zeros, they need to be trimmed first and it can be done at the cost of another byte.

Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.