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

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.

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

• related
– RGS
Feb 25, 2020 at 7:28
• 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} Feb 25, 2020 at 10:00
• Note to self: never do test cases by hand and late at night again
– RGS
Feb 25, 2020 at 10:09
• @J42161217 thanks, I had skipped the test case with only x and counted wrong :p fixed!
– RGS
Feb 25, 2020 at 10:10
• Also in first test case 15/4 = 15/4 not 3 Feb 25, 2020 at 10:23

# MATL, 6 bytes

Y-PiQ)


The inputs contain the coefficients in order of decreasing powers.

### Explanation

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

• Really short answer! Didn't know of that "deconvolution" operation
– RGS
Feb 25, 2020 at 12:08

# Wolfram Language (Mathematica), 31 bytes

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


Try it online!

• Nice you managed to reduce the byte count!
– RGS
Feb 25, 2020 at 12:06
• 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.) Feb 25, 2020 at 21:22
• Unfortunately, SeriesCoefficient[#/#2,{x,0,#3}]& is two bytes longer. Feb 25, 2020 at 21:28
• @MichaelSeifert yes, I tried many things myself but they didn't work for all cases... Feb 25, 2020 at 22:28

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

• 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?
– RGS
Feb 25, 2020 at 12:08
• @RGS Yes, the last $q$ is the answer. Feb 25, 2020 at 18:45

# 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)[~k]
import numpy


Try it online!

• Turns out importing numpy gives a really short answer! +1 well played
– RGS
Feb 25, 2020 at 23:39

# Pari/GP, 24 bytes

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


Try it online!

• I see :p really short submission! Good job +1
– RGS
Feb 26, 2020 at 7:55