# Partial Fractions

Given an input of a string, output the partial fraction in string form.

The partial fraction decomposition of a rational fraction of the form $$\\frac{f(x)}{g(x)}\$$, where $$\f\$$ and $$\g\$$ are polynomials, is its expression as:

$$\frac{f(x)}{g(x)}=p(x)+\sum_j\frac{f_j(x)}{g_j(x)}$$

In this case $$\p\$$ is 0, because we assume that the numerator is smaller than the denominator.

### Input:

In the form of an a list of the coefficients:

[[1, 4], [[1,3], [1,3]]]


For (x+4)/(x+3)^2.

### Output:

In the form of a list too:

[[[1], [1, 3]], [[1], [1, 6, 9]]]


For 1/(x+3) + 1/(x+3)^2.

### Assumptions

• The power of - x^ can be of any power greater than 1
• The fractions are factorised whenever possible
• You can output the elements of a list or the list itself
• You can take the input as a list or separate elements
• The numerator highest degree is always lower than the denominator highest degree
• You can take the input and output in any order
• The input will not be in a way such that the numerator and denominator have a factor in common
• You can assume all inputs take this form: $$\frac{something}{(something)(something)(...)}$$
• Note there can be multiple fractions e.g.: $$\frac{x+4}{(x+1)(x-2)(x+3)^2}$$

## Note:

This is not as easy as it looks This only gets harder. There are multiple cases to follow:

1. Linear factors

$$\frac{N(x)}{(ax+b)(cx+d)}=\frac{A}{ax+b}+\frac{B}{cx+d}$$

1. Repeated linear factors

$$\frac{N(x)}{(ax+b)^2}=\frac{A}{ax+b}+\frac{B}{(ax+b)^2}$$

$$\frac{N(x)}{(ax+b)(x^2+bx+c)}=\frac{A}{ax+b}+\frac{Bx+C}{x^2+bx+c}$$

### Testcases

Case 1:
[1,4], [[1,3], [1,2]] -> [[-1], [1,3]], [[2], [1,2]]


$$\frac{x+4}{(x+3)(x+2)}=\frac{-1}{x+3}+\frac{2}{x+2}$$

Case 2:
[1,4], [[1,3], [1,3]] -> [[1], [1,3]], [[1], [[1,3], [1,3]]]


$$\frac{x+4}{(x+3)^2}=\frac{1}{x+3}+\frac{1}{(x+3)^2}$$

Case 3:
[2,-1,4], [[1,0], [1,0,4]] -> [[1], [1,0]], [[1,-1], [1,0,4]]


$$\frac{2x^2-x+4}{x(x^2+4)}=\frac{1}{x}+\frac{x-1}{x^2+4}$$

• "It's not as easy as it looks" Well, it doesn't look particularly easy :P Commented Oct 11, 2022 at 14:14
• Are we to assume that the "somethings" in the denominator are no more than second order? Ie. will the denominator always be [L1, L2, ...] where Ln is no more than 3 elements? Commented Oct 11, 2022 at 15:32
• I feel like mathematica has a built in for this.... Commented Oct 11, 2022 at 16:20
• Could you provide a clearer explanation of the requirements, at the moment it just has a formula with four undefined terms ($p$, $j$, $f_j$, and $g_j$) - apart from the test cases I don't see what stops $p$ being the input with the sum being zero. What should the denominators ($g_j$?) of the terms in the output be? What is $p$ and what can we use it for? Commented Oct 11, 2022 at 16:22
• @Pacmanboss256 I guess reference.wolfram.com/language/ref/Apart.html? Commented Oct 11, 2022 at 16:27

# Python3, 1029 bytes:

import itertools as I
E=enumerate
U=lambda x:{len(x)-i:a for i,a in E(x,1)}
def G(v,r=[]):
if[]==v:yield r;return
for k in I.product(*[[-1,0,1]for _ in v[0]]):
N=[a+b for a,b in zip(v[0],k)]
if N[0]:yield from G(v[1:],r+[N])
else:yield from G(v[1:],r+[[-1]+N[1:]])
def P(p):
if[]==p:return{0:1}
s=U(p[0])
for e in p[1:]:
n={}
for i,a in E(e,1):
for A in s:n[A+len(e)-i]=n.get(A+len(e)-i,0)+s[A]*a
s=n
return s
T=lambda x:P([eval(i)for j,k in x for i in[j]*k])
H=lambda n,N:[1]+[0]*(max(n)-max(N))
def f(n,d):
S,D,M={*map(str,d)},[],{}
for i in S:Y=d.count(eval(i));D+=[(i,Y)]+[(i,1)]*(Y>1 and len(S)==1);M[i]=max(Y,M.get(i,0))
N=U(n);q,O=[[(a,b,t:=T([(j,M[j])for j in{*M}-{a}]+[(a,M[a]-b)]*(M[a]-b>0)),H(N,t))for a,b in D]],[]
while q:
a=q.pop(0)
O+=[a]
r={}
for *_,p,o in a:
for A,B in P([[*p.values()],o]).items():r[A]=r.get(A,0)+B
if r==N:return[[i[-1],[eval(i[0])]*int(i[1])]for i in a]
for i in G([j[-1]for j in a]):
v=[(A,B,C,z)for (A,B,C,_),z in zip(a,i)]
if v not in O:q+=[v]


Try it online!

• there's whitespace in the second to last line: for (A,B,C...)
– c--
Commented Oct 11, 2022 at 18:43
• suggest O+=[a:=q.pop(0)]
– c--
Commented Oct 11, 2022 at 18:49
• also from itertools import* saves a byte
– c--
Commented Oct 11, 2022 at 19:08
• yield from G(*N[0]and(v[1:],r+[N])or(v[1:],r+[[-1]+N[1:]])) also works
– c--
Commented Oct 11, 2022 at 19:19
• and for A in s:j=A+len(e)-i;n[j]=n.get(j,0)+s[A]*a
– c--
Commented Oct 11, 2022 at 19:53

# Mathematica, 124 bytes

#~CoefficientList~x&/@{Numerator@#,Denominator@#}&/@List@@Apart[First@#~FromDigits~x/Fold[Times,(#~FromDigits~x&)/@Last@#]]&


View it on Wolfram Cloud!

Apart does the heavy lifting here. The rest of the code allows it to work on the specified input and output format.

• @DialFrost I felt it was justified seeing as ~96% of the answer is for I/O ;) Commented Oct 12, 2022 at 4:21