20
\$\begingroup\$

Given a polynomial, determine whether it's prime.

A polynomial is ax^n + bx^(n-1) + ... + dx^3 + ex^2 + fx + g, where each term is a constant number (the coefficient) multiplied by a nonnegative integer power of x. The highest power with a nonzero coefficient is called the degree. For this challenge, we only consider polynomials of at least degree 1. That is, each polynomial contains some x. Also, we only use polynomials with integer coefficients.

Polynomials can be multiplied. For example, (x+3)(2x^2-2x+3) equals 2x^3+4x^2-3x+9. Thus, 2x^3+4x^2-3x+9 can be factored into x+3 and 2x^2-2x+3, so it is composite.

Other polynomials can not be factored. For example, 2x^2-2x+3 is not the product of any two polynomials (ignoring constant polynomials or those with non-integer coefficients). Hence, it is prime (also known as irreducible).

Rules

  • Input and output can be through any standard way.
  • Input can be a string like 2x^2-2x+3, a list of coeffecients like {2,-2,3}, or any similar means.
  • Output is either a truthy value if it's prime, or a falsey value if it's composite. You must yield the same truthy value for all primes, and the same falsey value for all composite polynomials.
  • The input will be of at least degree 1 and at most degree 10.
  • You may not use built-in tools for factorization (of integers or expressions) or equation solving.

Examples

True - prime

x+3
-2x
x^2+x+1
x^3-3x-1
-2x^6-3x^4+2
3x^9-8x^8-3x^7+2x^3-10

False - composite

x^2
x^2+2x+1
x^4+2x^3+3x^2+2x+1
-3x^7+5x^6-2x
x^9-8x^8+7x^7+19x^6-10x^5-35x^4-14x^3+36x^2+16x-12
\$\endgroup\$
  • 11
    \$\begingroup\$ From some quick googling this is a hard problem regardless of golfing. \$\endgroup\$ – orlp Mar 20 '15 at 18:15
  • 5
    \$\begingroup\$ Am I correct in thinking that by prime you mean irreducible? If so then this is basically a variant on this question about factoring polynomials, and I suspect that it won't attract any answers which don't factor. \$\endgroup\$ – Peter Taylor Mar 20 '15 at 19:20
  • 1
    \$\begingroup\$ According to this recent paper, "We are interested in the question of deciding whether a given polynomial is irreducible or not. Consequently, a simple test or criterion which would give this information is desirable. Unfortunately, no such criterion which will apply to all the classes of polynomials has yet been devised". \$\endgroup\$ – Peter Taylor Mar 20 '15 at 19:43
  • 2
    \$\begingroup\$ @AlexA., there are many many "if" tests which work for some polynomials, but the question is asking for an "if and only if" test which works for all polynomials. \$\endgroup\$ – Peter Taylor Mar 20 '15 at 20:07
  • 1
    \$\begingroup\$ This is a nice problem! Note that usually polynomials are only prime relative to a base ring (or field). In particular, if the field is the complex numbers, then no polynomial of degree greater than 2 is prime. So I would specify whether you want Rational (probably the most straightforward) Integer (this will involve some integer factoring as well), or modulo some number m. If m is prime, then there are rather easy algorithms. Otherwise things are a bit more tricky...(but feasible) \$\endgroup\$ – cody Mar 20 '15 at 20:46
3
+500
\$\begingroup\$

Mathematica, 224 bytes

f@p_:=(e=p~Exponent~x;r=Range[⌈e/-4⌉,(e+2)/4];e<2||FreeQ[PolynomialRemainder[p,Thread@{r,#}~InterpolatingPolynomial~x,x]&/@Tuples[#~Join~-#&[Join@@Position[#/Range@Abs@#,_Integer]]&/@#]~DeleteCases~{(a_)..},0|{}]&[p/.x->r])

Explanation:

Kronecker's method is used here. This method generates certain lower degree polynomials and tests whether there exists a factor of the original polynomial.

Test cases:

f/@{x+3, -2x, x^2+x+1, x^3-3x-1, -2x^6-3x^4+2, 3x^9-8x^8-3x^7+2x^3-10}
(* {True, True, True, True, True, True} *)

f/@{x^2, x^2+2x+1, x^4+2x^3+3x^2+2x+1, -3x^7+5x^6-2x, x^9-8x^8+7x^7+19x^6-10x^5-35x^4-14x^3+36x^2+16x-12}
(* {True, True, True, True, True} *)

It takes 14s on my laptop to conclude that 3x^9-8x^8-3x^7+2x^3-10 is prime.

\$\endgroup\$
1
\$\begingroup\$

PARI/GP, 16 bytes, cheap as hell

For some reason this wasn't disallowed (noting that the command doesn't factor or equation-solve):

polisirreducible

Test case

%(x^2+x+1)

returns 1 (true). The other examples work similarly.

But to show that this is solvable the hard way, here's a full solution.

Less cheap, but sloooooooooow

There's really no point golfing this.

Beauzamy(P)=
{
  my(d=poldegree(P),s,c);
  s=sum(i=0,d,polcoeff(P,i)^2/binomial(d,i));
  c = 3^(3/2 + d);
  c *= s / (4*d*Pi);
  abs(c * pollead(P))
}
factorpol(P)=
{
  my(B=Beauzamy(P)\1, t=B*2+1, d=poldegree(P)\2, Q);
  for(i=0,t^(d+1)-1,
    Q=Pol(apply(n->n-B, digits(i,t)));
    if(Q && poldegree(Q) && P%Q==0, return(Q))
  );
  0
}
irr(P)=
{
  factorpol(P)==0
}

Edit: Commenters have pointed out that the first method may be disallowed by good taste, the spirit of the rules, the Geneva Convention, standard loophole rules, etc. I don't agree, but in any case I posted the second version along with the first and certainly it seems acceptable.

\$\endgroup\$
  • 1
    \$\begingroup\$ Hmmmm... I'm pretty sure that this command does factor and/or solve equations under the hood. (Also, if a challenge disallows certain built-ins is kinda implied that a built-in that just solves the problem is also not in the spirit of the challenge.) \$\endgroup\$ – Martin Ender Apr 30 '15 at 18:05
  • \$\begingroup\$ @MartinBüttner: I think that the first answer fits the letter, but not the spirit, of the challenge's rules. That's why I wrote the second version, which is a legitimate solution. It can check that x^4+1 (which is famously reducible mod any prime) is irreducible in 86 milliseconds. If nothing else others can adapt and golf this version. \$\endgroup\$ – Charles Apr 30 '15 at 18:07
  • 1
    \$\begingroup\$ The first answer falls in a loophole which is banned by default: Using built-in functions to do the work. Please remove it from your answer, or at least indicate that it is not a valid solution. \$\endgroup\$ – isaacg Apr 30 '15 at 18:17
  • 5
    \$\begingroup\$ @isaacg That is not currently a valid standard loophole (due to the vote breakdown +44/-29). Charles, if you agree that only the second answer is really legitimate, then you should include its byte count instead. \$\endgroup\$ – Martin Ender Apr 30 '15 at 18:22
  • \$\begingroup\$ @MartinBüttner: I don't -- I think both are legitimate by the rules of this question and the general loopholes thread. But I added a comment to point out the issue. \$\endgroup\$ – Charles Apr 30 '15 at 18:27

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.