Computing a specific coefficient in a quotient of polynomials

Question

Context

After "Computing a specific coefficient in a product of polynomials", asking you to compute a specific coefficient of polynomial multiplication, I wish to create a "mirror" challenge, asking you to compute a specific coefficient from polynomial division.

Polynomial division

Let us establish an analogy with integer division. If you have two integers a and b, then there is a unique way of writing a = qb + r, with q, r integers and 0 <= r < b.

Let p(x), a(x) be two polynomials. Then there is a unique way of writing a(x) = q(x)p(x) + r(x), where q(x), r(x) are two polynomials and the degree of r(x) is strictly less than the degree of p(x).

Algorithm

Polynomial division can be performed through an iterative algorithm:

1. Initialize the quotient at q(x) = 0
2. While the degree of a(x) is at least as big as the degree of p(x):
   • let n = degree(a) - degree(p), let A be the coefficient of the term of highest degree in a(x) and P be the coefficient of highest degree in p(x).
   • do q(x) = q(x) + (A/P)x^n
   • update a(x) = a(x) - p(x)(A/P)x^n
3. q(x) is the quotient and what is left at a(x) is the remainder, which for our case will always be 0.

Task

Given two polynomials a(x), p(x) such that there exists q(x) satisfying a(x) = p(x)q(x) (with all three polynomials having integer coefficients), find the coefficient of q(x) of degree k.

(Yes, we are assuming the remainder is 0)

Input

Two polynomials (with integer coefficients) and an integer.

Each input polynomial can be in any sensible format. A few suggestions come to mind:

• A string, like "1 + 3x + 5x^2"
• A list of coefficients where index encodes exponent, like [1, 3, 5]
• A list of (coefficient, exponent) pairs, like [(1, 0), (3, 1), (5, 2)]

An input format must be sensible AND completely unambiguous over the input space.

The integer k is a non-negative integer. You may take it in any of the usual ways. You can assume k is less than or equal to the differences of the degrees of a(x) and p(x), i.e. k <= deg(a) - deg(p) and you can assume deg(a) >= deg(p).

Output

The integer corresponding to the coefficient of x^k in the polynomial q(x) that satisfies the equality a(x) = q(x)p(x).

Test cases

The input order for the test cases is a(x), p(x), integer k.

[12], [4], 0 -> 3
[0, 0, 6], [0, 3], 0 -> 0
[0, 0, 6], [0, 3], 1 -> 2
[0, 70, 70, 17, 70, 61, 6], [0, 10, 10, 1], 0 -> 7
[0, 70, 70, 17, 70, 61, 6], [0, 10, 10, 1], 1 -> 0
[0, 70, 70, 17, 70, 61, 6], [0, 10, 10, 1], 2 -> 1
[0, 70, 70, 17, 70, 61, 6], [0, 10, 10, 1], 3 -> 6
[0, -50, 20, -35, -173, -80, 2, -9, -10, -1], [0, 10, 10, 1], 0 -> -5
[0, -50, 20, -35, -173, -80, 2, -9, -10, -1], [0, 10, 10, 1], 1 -> 7
[0, -50, 20, -35, -173, -80, 2, -9, -10, -1], [0, 10, 10, 1], 2 -> -10
[0, -50, 20, -35, -173, -80, 2, -9, -10, -1], [0, 10, 10, 1], 3 -> -8
[0, -50, 20, -35, -173, -80, 2, -9, -10, -1], [0, 10, 10, 1], 4 -> 1
[0, -50, 20, -35, -173, -80, 2, -9, -10, -1], [0, 10, 10, 1], 5 -> 0
[0, -50, 20, -35, -173, -80, 2, -9, -10, -1], [0, 10, 10, 1], 6 -> -1

---

This is code-golf so shortest submission in bytes, wins! If you liked this challenge, consider upvoting it... And happy golfing!

(This is not part of the RGS Golfing Showdown)

• RGS: related
• ZaMoC: The 4,5,6 examples are wrong: q(x)=7 + x^2 + 6 x^3 so coefficients {0,1,2,3} = {7,0,1,6}
• RGS: Note to self: never do test cases by hand and late at night again
• RGS: @J42161217 thanks, I had skipped the test case with only x and counted wrong :p fixed!
• ZaMoC: Also in first test case 15/4 = 15/4 not 3

Answer 1

MATL, 6 bytes

Y-PiQ)

The inputs contain the coefficients in order of decreasing powers.

Try it online! Or verify all test cases

Explanation

(De) convolution is the key to success

 % Implicit inputs: two numerical vectors
Y- % Deconvolution 
P % Flip
i % Input: integer
Q % Add 1
) % Get the entry at that position
 % Implicit display

• RGS: Really short answer! Didn't know of that "deconvolution" operation

Answer 2

Wolfram Language (Mathematica), 31 bytes

Coefficient[Factor[#/#2],x,#3]&

Try it online!

• RGS: Nice you managed to reduce the byte count!
• Michael Seifert: A different approach with the same byte count: Limit[D[#/#2,{x,#3}]/#3!,x->0]& (It calculates the kth-order coefficient in the Taylor series of the quotient, which will just be the polynomial coefficient. Note that setting x to 0 via ... /.x->0 doesn't work for all polynomials.)
• Michael Seifert: Unfortunately, SeriesCoefficient[#/#2,{x,0,#3}]& is two bytes longer.
• ZaMoC: @MichaelSeifert yes, I tried many things myself but they didn't work for all cases...

Answer 3

JavaScript (ES6), 81 bytes

Takes input as (a,p,k). The polynomial coefficients are expected from highest to lowest.

(a,[c,...p],k)=>a.slice(p.length+k).map((_,n)=>p.map(v=>a[++n]-=v*q,q=a[n]/c))&&q

Try it online!

• RGS: What is going on with the &&q at the end? Is it just to return the coefficient you want? q stores the intermediate coefficients of the quotient, right?
• Arnauld: @RGS Yes, the last \$q\$ is the answer.

Answer 4

Python 3, (削除) 51 49 (削除ここまで) 48 bytes

Input: a, p, k. The format for the polynomials a and p is a list of coefficients, in order of highest to lowest degree.

lambda*p,k:numpy.polydiv(*p)[0][~k]
import numpy

Try it online!

• RGS: Turns out importing numpy gives a really short answer! +1 well played

Answer 5

Pari/GP, 24 bytes

f(a,p,k)=polcoeff(a/p,k)

Try it online!

• RGS: I see :p really short submission! Good job +1