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!

• Erik the Outgolfer: Note: Before voting to close, please consider that this question is not a duplicate of this one. I can think of at least one approach to this problem which will not be trivially modifiable for the other challenge (although I'm not saying what; that's left to you ;P).
• Οurous: Can we assume we only need to return roots inside the integer bounds of our language? Or should the algorithm work even if the languages integer type range was increased, but the behaviour stayed the same.
• flawr: Can we also use a native polynomial type if your language supports those?
• Jack M: Are programs that run forever if there are no solutions accepted?
• Manish Kundu: That's to keep things simple.

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]

• mathmandan: As an alternative to Rouche's Theorem, the Rational Roots Theorem would also suffice to justify the bound you used. By the Rational Roots Theorem, all integer roots are bounded in absolute value by the maximum of the absolute values of the coefficients, a tighter bound than the sum. Or even tighter, by the absolute value of the "last" nonzero coefficient--i.e. the coefficient of the smallest power of x which has a nonzero coefficient. (Probably doesn't help save any bytes, just an alternative proof since the RRT is probably more familiar than Rouche to most folks.) :)
• Giuseppe: @mathmandan that approach is three bytes longer: Try it here, although I'm sure I've missed a trick or two
• Luis Mendo: @Giuseppe Thanks to both. Maybe X>t_w&:GyZQ~), but still 13 bytes
• Luis Mendo: ... but I found a shorter alternative for the range

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

• Zgarb: You could do ṁṡ instead of oṡ►a if you deduplicate later.
• H.PWiz: @Zgarb Very nice! Thanks

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.

• nimi: You can iterate i over [minBound..] and drop the whole t thing. Call f with explicit Int lists, e.g. f [1::Int,5,6]. Of course this doesn't finish in reasonable time.
• totallyhuman: @nimi Why would that ever stop? Wouldn't it infinitely loop?
• nimi: No, Bounded types stop at maxBound, e.g. print [minBound::Bool ..].

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!

• ovs: 91 bytes
• Rod: @LuisMendo yes.
• Zgarb: Our current consensus seems to be that programs must always terminate, unless the challenge states otherwise.
• Rod: @Zgarb there, fixed!
• Mr. Xcoder: Using numpy.polyval saves quite a few bytes

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!

• Not a tree: I think you can use #.# instead of Tr@Abs@#: it's a worse bound but fewer bytes.
• IridescenceDeep: OP said in a comment that you could use your language's native polynomial type if one exists. I don't know Mathematica well but I imagine there is one... Would that save bytes?
• alephalpha: It fails when 0 is a root.
• Kelly Lowder: @alephalpha, fixed.
• Roman: 24 bytes with a Default pattern and an operator right-composition

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!

• Kelly Lowder: This fails as currently stated with 1,2,1 as it repeats the root and the OP said they had to be distinct. You need Union to fix that.
• celtschk: @KellyLowder: Ah, I missed that. But then, it was also missing in the given test cases.
• celtschk: @KellyLowder: I've now fixed it. In case you downvoted because of this, can you please revert it?
• Kelly Lowder: @cellschk, yep done.
• Roman: 29 bytes by using an undocumented feature of Solve: the list of variables can be omitted.

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
}

• mathmandan: (I think you could use the max of the absolute values instead of the sum; this wouldn't change the byte count, but it ought to improve performance.) Anyway, yes, pity the shorter version doesn't work with a_0==0. Is there some short way in R to search for the first (with powers ascending) nonzero coefficient, and use that instead? This would correspond to factoring out as many x's as possible first (of course, then you'd have to remember to output 0 also, which would presumably cost some bytes.)
• Giuseppe: @mathmandan max would be more efficient, but to your second point, as I don't have to worry about outputting 0 since it's generated by the range -t:t (where t is the first nonzero coefficient), it saves 2 bytes!
• mathmandan: Oh, very nice! (And a beautiful explanation as well.)

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.

• Jonathan Allan: Is there something I'm missing about taking the (allowed) reverse order and doing Ær+.Ḟ?
• Jonathan Allan: I'm slightly confused since the Python answer with numpy isn't doing so either, and am thinking I've missed some edge case.
• Mr. Xcoder: @JonathanAllan As I expected, yours fails for [1,2,3].
• Jonathan Allan: "If there is no solution for the given equation, then the output is undefined"
• Mr. Xcoder: @JonathanAllan But it does fail for [10,-42,8], right?

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!

• Kevin Cruijssen: l+~j++ can be golfed to l-++j
• Jonathan Frech: @KevinCruijssen Thanks a lot.
• Jonathan Frech: @ceilingcat Thank you.

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!