# 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 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 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} – J42161217 Feb 25 at 10:00
• Note to self: never do test cases by hand and late at night again – RGS Feb 25 at 10:09
• @J42161217 thanks, I had skipped the test case with only x and counted wrong :p fixed! – RGS Feb 25 at 10:10
• Also in first test case 15/4 = 15/4 not 3 – J42161217 Feb 25 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
Q    % Add 1
)    % Get the entry at that position
% Implicit display

• Really short answer! Didn't know of that "deconvolution" operation – RGS Feb 25 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 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.) – Michael Seifert Feb 25 at 21:22
• Unfortunately, SeriesCoefficient[#/#2,{x,0,#3}]& is two bytes longer. – Michael Seifert Feb 25 at 21:28
• @MichaelSeifert yes, I tried many things myself but they didn't work for all cases... – J42161217 Feb 25 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 at 12:08
• @RGS Yes, the last $q$ is the answer. – Arnauld Feb 25 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)[0][~k]
import numpy


Try it online!

• Turns out importing numpy gives a really short answer! +1 well played – RGS Feb 25 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 at 7:55