Multiplicity of a root of a polynomial

Question

Let \$p(x)\$ be a polynomial. We say \$a\$ is a root of multiplicity \$k\$ of \$p(x)\$, if there is another polynomial \$s(x)\$ such that \$p(x)=s(x)(x-a)^k\$ and \$s(a)\ne0\$.

For example, the polynomial \$p(x)=x^3+2x^2-7x+4=(x+4)(x-1)^2\$ has \$1\$ and \$-4\$ as roots. \$1\$ is a root of multiplicity \$2\$. \$-4\$ is a root of multiplicity \$1\$.

Task

Given a nonzero polynomial \$p(x)\$ and a root \$a\$ of it, find the multiplicity of \$a\$.

The coefficients of \$p(x)\$ are all integers. \$a\$ is also an integer.

You may take the polynomial in any reasonable format. For example, the polynomial \$x^4-4x^3+5x^2-2x\$ may be represented as:

• a list of coefficients, in descending order: [1,-4,5,-2,0];
• a list of coefficients, in ascending order:[0,-2,5,-4,1];
• a string representation of the polynomial, with a chosen variable, e.g., x: "x^4-4*x^3+5*x^2-2*x";
• a built-in polynomial object, e.g., x^4-4*x^3+5*x^2-2*x in PARI/GP.

When you take input as a list of coefficients, you may assume that the leading coefficient (the first one in descending order) is nonzero.

This is code-golf, so the shortest code in bytes wins.

Testcases

Here I use coefficient lists in descending order:

[1,2,-7,4], 1 -> 2
[1,2,-7,4], -4 -> 1
[1,-4,5,-2,0], 0 -> 1
[1,-4,5,-2,0], 1 -> 2
[1,-4,5,-2,0], 2 -> 1
[4,0,-4,4,1,-2,1], -1 -> 2
[1,-12,60,-160,240,-192,64,0], 2 -> 6

Answer 1

Jelly, 3 bytes

Ærċ

Try it online!

Takes input as a list of coefficients in ascending order. The Footer on TIO reverses each of the test cases to fit this.

How it works

Ærċ - Main link. Takes a polynomial P on the left, and a root r on the right
Ær  - Calculate the roots of P, with repeats
  ċ - Count the number of times r appears in the list of roots

Answer 2

JavaScript (ES7), 62 bytes

Expects (root)(polynomial), where polynomial is a list of coefficients in ascending order.

(r,s=0)=>g=p=>s?-1:1+g(p.map((c,i)=>(s+=c*r**i,c*i)).slice(1))

Try it online!

How?

This simply recursively computes the successive derivatives of the polynomial:

$$P_{k+1}(x)=\frac{d}{dx}P_k(x)$$

until \$P_k(r)\neq 0\$ and returns the number of iterations.

Commented

(                   // outer function taking:
  r,                //   the root r
  s = 0             //   the sum s of the polynomial evaluation
) =>                //
g = p =>            // inner recursive function taking the polynomial p[]
s ?                 // if s is not equal to 0:
  -1                //   stop the recursion and decrement the final result
:                   // else:
  1 +               //   increment the final result
  g(                //   do a recursive call with the derivative of p[]:
    p.map((c, i) => //     for each coefficient c at position i in p[]:
      (             //
        s +=        //       add to s:
          c *       //         the coefficient multiplied by
          r ** i,   //         the root raised to the power of i
        c * i       //       set the new coefficient to c * i
      )             //
    ).slice(1)      //     end of map(); remove the leading term
  )                 //   end of recursive call

---

59 bytes

A version without slice() suggested by @tsh.

(r,s=k=0)=>g=p=>s?~k:g(p.map(c=>(s+=0|c*r**i,c*i++),i=k--))

Try it online!

Answer 3

Python 3.8 (pre-release), 65 bytes

f=lambda p,r,c=0:(q:=[c:=b+c*r for b in p])!=c==0and-~f(q[:-1],r)

Try it online!

Divides by the linear factor X-root and recurses if the remainder is zero.

Answer 4

Factor + math.polynomials, 58 bytes

[ [ 2dup polyval 0 = ] [ dup pdiff swap ] produce length ]

Try it online!

Takes root polynomial where the polynomial is given as a sequence of coefficients in ascending order. Uses the method described in Arnauld's JavaScript answer. polyval evaluates a polynomial given a value and pdiff computes the derivative of a polynomial. produce creates a list of successive derivatives until one evaluates to nonzero. Then take the length of the list.

Answer 5

Rust, 105 bytes

|a,r|{let mut j=0;while 0==(0..).zip(&mut*a).map(|(i,c)|{let d=*c*r.pow(i);*c*=i as i32;d}).sum(){j+=1}j}

Try it online!

It's a fn(&mut[i32], i32) -> usize. Uses the same approach as Arnauld's JS answer.

Answer 6

Mathematica, 19 bytes

#~Roots~x~Count~#2&

Takes inputs as equations: polynomial == 0, x == root.

If this is not allowed:

Mathematica, 27 bytes:

Count[Roots[#==0,x],x==#2]&

View them on Wolfram Cloud!

Answer 7

Maxima, 29 bytes

f(p,a):=hipow(factor(p),x-a);

Try it online!

Factorises \$p(x)\$, taken as a built-in polynomial object, and returns the exponent of \$x-a\$.

Answer 8

SageMath, 29 bytes

lambda p,a:dict(p.roots())[a]

Try it online!

Inputs a polynomial \$p\$ and a root \$a\$ of \$p\$.
Uses p.roots() which returns the roots of \$p\$ along with their multiplicity as a list of \$2\$-element tuples. Turning this into a dictionary requires only a simple lookup of the root to find its multiplicity.

Answer 9

Desmos, 103 bytes

k=l.length
L=[0...k-1]
I=[n...k-1]
f(l,R)=L[[0^{total(R^{[0...k-n]}I!l[n+1...]/(I-n)!)^2}forn=L]=0].min

Try It On Desmos!

Try It On Desmos! - Prettified

Function \$f(l,R)\$ takes in a list of coefficients in ascending order and the root \$R\$.

Uses Arnauld's strategy of repeatedly taking derivatives, so go upvote his answer too!

There's probably a way of shortening the L=[...] I=[...] part since they are so similar but I don't see it at the moment.

Might post an explanation if I feel like it, though if you understand Desmos enough it shouldn't be too hard to decipher.

Answer 10

Charcoal, 21 bytes

Ｗ¬↨⮌θη≔ΦＥθ×κλλθＩ⁻ＬＡＬθ

Try it online! Link is to verbose version of code. Explanation: Uses the same differentiation trick as @Arnauld's answer.

Ｗ¬↨⮌θη

While the root is a root of the current polynomial (defaulting to the input polynomial) (using base conversion of the reversed polynomial to evaluate it)...

≔ΦＥθ×κλλθ

... differentiate the polynomial.

Ｉ⁻ＬＡＬθ

Output the difference in degree of the input and final polynomial.

Answer 11

Raku, 51 bytes

{((|@^p,0),*[^(*-1)].produce(*×$^r+*)...*[*-1])-2}

Try it online!

This is an anonymous function that takes a polynomial as an array of coefficients in descending order, and a root. The arguments are stored in the placeholder variables @^p and $^r respectively.

The outermost parenthesized expression is a list, where each element is a list of polynomial coefficients followed by a remainder. (|@p, 0) is the first element of the list, the input polynomial with a zero remainder appended. Each successive term is the previous polynomial divided by \$x - r\$. The iteration ends when the the remainder term, *[*-1], is nonzero/truthy.

*[^(*-1)] strips off the final remainder element of the previous coefficient/remainder list, and .produce(* × $^r + *) performs polynomial long division by \$x - r\$.

Finally, the - 2 coerces the entire list of polynomials to a number, its length, and subtracting 2 gives the multiplicity of the root.

Answer 12

GeoGebra, 66 bytes

f=x
InputBox(f
k
InputBox(k
l=Flatten(Factors(f
l(IndexOf(x-k,l)+1

Input the polynomial in the first Input Box, and the root in the second Input Box.

All the heavy lifting is done by the built-in Factors.

Try It On GeoGebra!

Answer 13

Japt, 20 bytes

I don't understand the challenge! So a port of Arnauld's solution will have to do for now.

T?J:Òß¡T±X*VpY X*YÃÅ

Try it

T?J:Òß¡T±X*VpY X*YÃÅ     :Implicit input of array U & integer V
T?                       :If T (initially 0) is truthy (not 0) then return
  J                      :  -1
   :                     :Else
    Ò                    :  Negate the bitwise NOT of (i.e., increment)
     ß                   :  Recursive call with argument (The unchanged V is implicit)
      ¡                  :    Map each X at 0-based index Y in U
       T±                :      Increment T by
         X*VpY           :      X multiplied by V raised to the power of Y
               X*Y       :      Return X*Y
                  Ã      :    End Map
                   Å     :    Slice off the first element

Answer 14

J, 14 11 bytes

-3 bytes thanks to Bubbler

+/@E.1{::p.

Accepts a list of coefficients in ascending order

Attempt This Online!

+/@E.1{::p.
     1{::p. NB. monadic fork
         p. NB. computes boxed result of multipler;roots
     1{::   NB. fetches and lists contents of second box
+/@E.       NB. x E. y finds occurrences of x in y, returns boolean list
  @         NB. atop, executes E. dyadically and +/ monadically
+/          NB. sum reduce

Answer 15

PARI/GP, 23 bytes

Naïve solution:

(P,r)->valuation(P,x-r)

Answer 16

Scala, 116 bytes

Port of @corvus_192's Rust answer in Scala.

---

Ungolfed version. Try it online!

{(a,r)=>var j=0;while((0 until a.length).zip(a).map{case(i,c)=>val d=c*math.pow(r,i).toInt;a(i)*=i;d}.sum==0)j+=1;j}

Ungolfed version. Try it online!

object Main {
  def main(args: Array[String]): Unit = {
    val f: (Array[Int], Int) => Int = { (a, r) =>
      var j = 0
      while ((0 until a.length).zip(a).map {
        case (i, c) =>
          val d = c * math.pow(r, i).toInt
          a(i) *= i
          d
      }.sum == 0) j += 1
      j
    }

    assert(f(Array(4, -7, 2, 1), 1) == 2)
    assert(f(Array(4, -7, 2, 1), -4) == 1)
    assert(f(Array(0, 64, -192, 240, -160, 60, -12, 1), 2) == 6)
  }
}