Find Integral Roots of A Polynomial

Question

Challenge

The challenge is to write a program that takes the coefficients of any n-degree polynomial equation as input and returns the integral values of x for which the equation holds true. The coefficients will be provided as input in the order of decreasing or increasing power. You can assume all the coefficients to be integers.

Input And Output

The input will be the coefficients of the equation in decreasing or increasing order of power. The degree of the equation, i.e, maximum power of x, is always 1 less than the total no of elements in the input.

For example:

[1,2,3,4,5] -> represents x^4 + 2x^3 + 3x^2 + 4x + 5 = 0 (degree = 4, as there are 5 elements)
[4,0,0,3] -> represents 4x^3 + 3 = 0 (degree = 3, as there are 3+1 = 4 elements)

Your output should be only the distinct integral values of x which satisfy the given equation. All the input coefficients are integers and the input polynomial will not be a zero polynomial. If there is no solution for the given equation, then the output is undefined.

If an equation has repeated roots, display that particular root only once. You can output the values in any order. Also, assume that the input will contain at-least 2 numbers.

Examples

[1,5,6] -> (-3,-2)
[10,-42,8] -> (4)
[1,-2,0] -> (0,2)
[1, 1, -39, -121, -10, 168] -> (-4, -3, -2, 1, 7)
[1, 0, -13, 0, 36] -> (-3, -2, 2, 3)
[1,-5] -> (5)
[1,2,3] -> -

Note that the equation in the second example also has the root 0.2, but it is not displayed as 0.2 is not an integer.

Scoring

This is code-golf, so the shortest code (in bytes) wins!

Answer 1

MATL, 13 12 bytes

|stE:-GyZQ~)

Try it online!

This uses the fact that, for integer coefficients, the absolute value of any root is strictly less than the sum of absolute values of the coefficients.

Explanation

Consider input [1 5 6] as an example.

|    % Implicit input. Absolute value
     % STACK: [1 5 6]
s    % Sum
     % STACK: 12
t    % Duplicate
     % STACK: 12, 12
E    % Multiply by 2
     % STACK: 12, 24
:    % Range
     % STACK: 12, [1 2 ... 23 24]
-    % Subtract, elemet-wise
     % STACK: [11 10 ... -11 -12]
G    % Push input again
     % STACK: [11 10 ... -11 -12], [1 5 6]
y    % Duplicate from below
     % STACK: [11 10 ... -11 -12], [1 5 6], [11 10 ... -11 -12]
ZQ   % Polyval: values of polynomial at specified inputs
     % STACK: [11 10 ... -11 -12], [182 156 ... 72 90]
~    % Logical negation: turns nonzero into zero
     % STACK: [11 10 ... -11 -12], [0 0 ... 0] (contains 1 for roots)
)    % Index: uses second input as a mask for the first. Implicit display
     % STACK: [-3 -2]

Answer 2

Husk, 10 9 bytes

-1 byte thanks to Zgarb

uSȯf¬`Bṁṡ

Try it online!

Explanation

       ṁṡ   Concatenate together the symmetric ranges of each coefficient
            (It is guaranteed that the integer roots lie in the range [-n..n],
                        where n is the coefficient with the largest magnitude)
 Sȯf        Find all the values in that range which
    ¬       are zero
     `B     when plugged through the polynomial
            (Base conversion acts as polynomial evaluation)
u           De-duplicate the roots

Answer 3

Haskell, 54 bytes

f l|t<-sum$abs<$>l=[i|i<-[-t..t],foldl1((+).(i*))l==0]

Try it online!

Brute force and synthetic division.

Ungolfed with UniHaskell and -XUnicodeSyntax

import UniHaskell

roots    ∷ Num a ⇒ [a] → [a]
roots xs = [r | r ← -bound … bound, foldl1 ((+) ∘ (r ×)) xs ≡ 0]
             where bound = sum $ abs § xs

Alternate solution, 44 bytes

Credit to nimi.

f l=[i|i<-[minBound..],foldl1((+).(i*))l==0]

Good luck with trying it online, as this checks every number in an Int's range.

Answer 4

Python 2 + numpy, 95 93 91 103 93 91 82 bytes

^{-2 bytes thanks to ovs
thanks Luis Mendo for the upper/lower bounds of the roots
-10 bytes thanks to Mr. Xcoder}

from numpy import*
def f(r):s=sum(fabs(r));q=arange(-s,s);print q[polyval(r,q)==0]

Try it online!

Answer 5

Wolfram Language (Mathematica), 50 47 42 25 27 bytes

{}⋃Select[x/.Solve[#~FromDigits~x==0],IntegerQ]&

Try it online!

Update: using Luis Mendo's fact, golfed off another 3 bytes

Pick[r=Range[s=-Tr@Abs@#,-s],#~FromDigits~r,0]&

Getting sloppier with the bounds, we can reduce this 5 more bytes per @Not a tree's suggestion:

Pick[r=Range[s=-#.#,-s],#~FromDigits~r,0]&

After posting this, OP commented allowing "native polynomials", so here's a 25 byte solution that accepts the polynomial as input. This works because by default Mathematica factors polynomials over the integers, and any rational roots show up in a form like m*x+b that fails the pattern match.

Cases[Factor@#,b_+x:>-b]&

As @alephalpha pointed out this will fail for the case where zero is a root, so to fix that we can use the Optional symbol :

Cases[Factor@#,b_:0+x:>-b]&

This parses fine Mathematica 11.0.1 but fails and requires an extra set of parentheses around b_:0 in version 11.2. This takes up back up to 27 bytes, plus two more after version 11.0.1. It looks like a "fix" was put in here

Try it Online!

Answer 6

Wolfram Language (Mathematica), 33 26 31 bytes

Fixed an error noted by Kelly Lowder in the comments.

x/.{}⋃Solve[#==0,x,Integers]&

Try it online!

Previous incorrect solutions:

I just noticed that for no integer solution, the output is undefined instead of empty list; that allows to remove a few bytes.

x/.Solve[#==0,x,Integers]&

Try it online!

Now if no integer solution exists, the function returns x.

Previously:

x/.Solve[#==0,x,Integers]/.x->{}&

Try it online!

Answer 7

R, 61 59 bytes

A special thanks to @mathmandan for pointing out my (incorrect) approach could be saved, and golfed!

function(p)(x=-(t=p[!!p][1]):t)[!outer(x,seq(p)-1,"^")%*%p]

Try it online!

Takes input as a list of coefficients in increasing order, i.e., c(-1,0,1) represents -1+0x+1x^2.

Using the rational root theorem, the following approach very nearly works, for 47 bytes:

function(p)(x=-p:p)[!outer(x,seq(p)-1,"^")%*%p]

Try it online!

-p:p generates a symmetric range (with a warning) using only the first element of p, a_0. By the Rational Root Theorem, all rational roots of P must be of the form p/q where p divides a_0 and q divides a_n (plus or minus). Hence, using just a_0 is sufficient for |a_0|>0, as for any q, |p/q|<=a_0. However, when a_0==0, as then any integer divides 0, and thus this fails.

However, mathmandan points out that really, in this case, this means that there's a constant factor of x^k that can be factored out, and, assuming k is maximal, we see that

P(x) = x^k(a_k + a_{k+1}x + ... a_n x^{n-k}) = x^k * Q(x)

We then apply the Rational Root Theorem to Q(x), and as a_k is guaranteed to be nonzero by the maximality of k, a_k provides a tidy bound for the integer roots of Q, and the roots of P are the roots of Q along with zero, so we will have all the integer roots of P by applying this method.

This is equivalent to finding the first nonzero coefficient of the polynomial, t=p[!!p][1] and using it instead of the naive p[1] as the bounds. Moreover, since the range -t:t always contains zero, applying P to this range would still give us zero as a root, if indeed it is.

ungolfed:

function(polynom) {
 bound <- polynom[polynom != 0][1]             #first nonzero value of polynom
 range <- -bound:bound                         #generates [-bound, ..., bound]
 powers <- outer(range,seq_along(p) - 1, "^")  #matrix where each row is [n^0,n^1,n^2,...,n^deg(p)]
 polyVals <- powers %*% polynom                #value of the polynomial @ each point in range
 return(range[polyVals == 0])                  #filter for zeros and return
}

Answer 8

Jelly, 8 bytes

ASŒRḅ@Ðḟ

Try it online! or as a test-suite!

How?

ASŒRḅ@Ðḟ || Full program (monadic link).

AS        || Sum the absolute values.
  ŒR      || And create the symmetric inclusive range from its negative value.
       Ðḟ || And discard those that yield a truthy value...
     ḅ@   || When plugging them into the polynomial (uses base convertion).

Based off Luis' answer. An alternative.

Answer 9

Octave, 59 49 bytes

@(p)(x=-(t=p(~~p)(end)):sign(t):t)(!polyval(p,x))

Try it online!

This is a port of my R answer. The only difference is that I have to explicitly use sign(t) and end to generate the range, and that it has polyval to compute the polynomial.

Takes input as a row vector of coefficients in decreasing order.

Answer 10

Pari/GP, 31 bytes

p->[x-a|a<-factor(p)[,1],a'==1]

Factors the polynomial, and picks out the factors whose derivatives are 1.

Try it online!

Answer 11

C (gcc), 127 126 123 bytes

• Saved one byte thanks to Kevin Cruijssen; golfing l+~j++ to l-++j.
• Thanks to ceilingcat for saving three bytes.

x,X,j,m,p;f(A,l)int*A;{for(m=j=0;j<l;m+=abs(A[j++]));for(x=~m;X=x++<m;p||printf("%d,",x))for(p=j=0;j<l;X*=x)p+=A[l-++j]*X;}

Try it online!

---

Explanation

C (gcc), 517 bytes

x,X,j,m,p;                      // global integer variables
f(A,l)int*A;{                   // define function, takes in integer array pointer and length
 for(m=j=0;j<l;m+=abs(A[j++])); // loop through array, sum up absolute values
  for(x=~m;X=x++<m;             // loop through all values x in [-m, m], prime X
   p||printf("%d,",x))          // at loop's end, print x value if polynomial value is zero
    for(p=j=0;j<l;X*=x)         // loop through coefficients
     p+=A[l-++j]*X;}            // build polynomial

Try it online!

Answer 12

Java 8, 141 140 bytes

a->{int l=a.length,s=0,i,r,f,p;for(int n:a)s+=n<0?-n:n;for(r=~s;r++<s;System.out.print(p==0?r+",":""))for(p=i=0,f=1;i<l;f*=r)p+=a[l-++i]*f;}

Inspired by @Rod's Python 2 answer (his 82 bytes version).

Fun challenge! I certainly learned a lot of it when investigating about polynomials and seeing how some others here have done it.

Explanation:

Try it online.

a->{                   // Method with integer-array parameter and no return-type
  int l=a.length,      //  The length of the input-array
      s=0,             //  Sum-integer, starting at 0
      i,               //  Index integer
      r,               //  Range-integer
      f,               //  Factor-integer
      p;               //  Polynomial-integer
  for(int n:a)         //  Loop over the input-array
    s+=n<0?-n:n;       //   And sum their absolute values
  for(r=~s;r++<s;      //  Loop `r` from `-s` up to `s` (inclusive) (where `s` is the sum)
      System.out.print(p==0?r+",":""))
                       //    After every iteration: print the current `r` if `p` is 0
    for(p=i=0,         //   Reset `p` to 0
        f=1;           //   and `f` to 1
        i<l;           //   Loop over the input-array again, this time with index (`i`)
        f*=r)          //     After every iteration: multiply `f` with the current `r`
      p+=              //    Sum the Polynomial-integer `p` with:
         a[l-++i]      //     The value of the input at index `l-i-1`,
                 *f;}  //     multiplied with the current factor `f`

Answer 13

Octave with Symbolic Package, 63 bytes

@(p)(s=double(solve(poly2sym(p)==0)))(s==(t=real(s))&~mod(t,1))

Try it online!

Answer 14

05AB1E, 8 bytes

ÄOD(Ÿʒβ>

Try it online!

Answer 15

JavaScript (ES6), 97 bytes

a=>[...Array((n=Math.max(...a.map(Math.abs)))-~n)].map(_=>n--).filter(i=>!a.reduce((x,y)=>x*i+y))

Takes coefficients in decreasing order of power and outputs results in descending order.

Answer 16

Clean, 110 91 bytes

import StdEnv
?p#s=sum p
=[i\\i<-[~s..s]|i<>0&&sum[e*i^t\\t<-reverse(indexList p)&e<-p]==0]

Try it online!

Answer 17

Python 2, 89 bytes

def f(a):s=sum(map(abs,a));return[n for n in range(-s,s)if reduce(lambda v,c:v*n+c,a)==0]

Try it online!