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]
\$\endgroup\$
  • \$\begingroup\$ May I take in the degree of the polynomial as well as the polynomial \$\endgroup\$ – Rohan Jhunjhunwala May 14 '17 at 15:19
  • \$\begingroup\$ Yes I think that is acceptable. \$\endgroup\$ – flawr May 14 '17 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 '17 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 '17 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 '17 at 19:48

10 Answers 10

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]&
\$\endgroup\$
  • 5
    \$\begingroup\$ And you didn't even need any builtins! \$\endgroup\$ – Neil May 14 '17 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 '17 at 17:14
  • \$\begingroup\$ I would upvote this twice if I could \$\endgroup\$ – Greg Martin May 14 '17 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 '17 at 0:16
6
\$\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.

\$\endgroup\$
  • \$\begingroup\$ So, we need not touch the 2,4th,6th, 8th etc? \$\endgroup\$ – Rohan Jhunjhunwala May 14 '17 at 15:19
  • 2
    \$\begingroup\$ Those are zero anyway. \$\endgroup\$ – flawr May 14 '17 at 15:21
  • \$\begingroup\$ Your trick with ı*Ċ is very nice, you should explain it :) \$\endgroup\$ – Leo May 14 '17 at 19:01
  • \$\begingroup\$ @Leo It's essentially a straightforward implementation though... \$\endgroup\$ – Leaky Nun May 15 '17 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 '17 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.

\$\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.

\$\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!

\$\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.

\$\endgroup\$
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

\$\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.

\$\endgroup\$
0
\$\begingroup\$

Pari/GP, 16 bytes

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

Try it online!

\$\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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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