# Multiplicity of a root of a polynomial

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

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 , 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

• Commented Oct 16, 2022 at 13:35

# 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


# 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!

• (r,s=k=0)=>g=p=>s?~k:g(p.map(c=>(s+=0|c*r**i,c*i++),i=k--))
– tsh
Commented Oct 17, 2022 at 1:16

# 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.

• Nice method! This taught me that when evaluating a polynomial at a value r with Horner's method, the intermediate results are also the coefficients obtained by dividing out by x-r.
– xnor
Commented Oct 17, 2022 at 23:34
• Amazing what you can do with lambda and list comprehensions. Here is a Python gist of call graph of f(*([1,-12,60,-160,240,-192,64,0], 2)). Commented Oct 18, 2022 at 20:08

# 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.

# 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.

# 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!

• #2~CountRoots~{,#,#}& inputting root, polynomial in Null for 21 on the 2nd
– att
Commented Oct 18, 2022 at 1:11

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

# 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.

# 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.

# 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.

# 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.

• x-r is not a monomial. Commented Oct 16, 2022 at 22:51
• @loopywalt Huh, true enough. Fixed.
– Sean
Commented Oct 17, 2022 at 0:19

# 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!

# 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


# 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.
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. sum reduce

• 11 bytes: +/@E.1{::p. Commented Oct 18, 2022 at 1:06
• How does this work? Commented Oct 18, 2022 at 5:55
• The train has even number of parts +/@E. 1 {:: p., so it is parsed as a hook +/@E. (1 {:: p.) meaning x +/@E. (1 {:: p.) y. Commented Oct 18, 2022 at 7:01
• Smart. I find myself blind to hooks a lot. Thanks Commented Oct 18, 2022 at 14:50

# PARI/GP, 23 bytes

Naïve solution:

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


# 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)
}
}