18
\$\begingroup\$

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 , 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
\$\endgroup\$
1

16 Answers 16

6
\$\begingroup\$

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
\$\endgroup\$
6
\$\begingroup\$

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!

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

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.

\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$
    – xnor
    Oct 17, 2022 at 23:34
  • \$\begingroup\$ 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)). \$\endgroup\$
    – Galen
    Oct 18, 2022 at 20:08
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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!

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

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

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

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

Charcoal, 21 bytes

W¬↨⮌θη≔ΦEθ×κλλθI⁻LALθ

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

W¬↨⮌θη

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

≔ΦEθ×κλλθ

... differentiate the polynomial.

I⁻LALθ

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

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

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.

\$\endgroup\$
2
  • \$\begingroup\$ x-r is not a monomial. \$\endgroup\$
    – loopy walt
    Oct 16, 2022 at 22:51
  • \$\begingroup\$ @loopywalt Huh, true enough. Fixed. \$\endgroup\$
    – Sean
    Oct 17, 2022 at 0:19
1
\$\begingroup\$

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!

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

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
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
4
  • \$\begingroup\$ 11 bytes: +/@E.1{::p. \$\endgroup\$
    – Bubbler
    Oct 18, 2022 at 1:06
  • \$\begingroup\$ How does this work? \$\endgroup\$
    – south
    Oct 18, 2022 at 5:55
  • \$\begingroup\$ 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. \$\endgroup\$
    – Bubbler
    Oct 18, 2022 at 7:01
  • \$\begingroup\$ Smart. I find myself blind to hooks a lot. Thanks \$\endgroup\$
    – south
    Oct 18, 2022 at 14:50
1
\$\begingroup\$

PARI/GP, 23 bytes

Naïve solution:

(P,r)->valuation(P,x-r)
\$\endgroup\$
1
\$\begingroup\$

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)
  }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.