SymPy result Filtering

Question

I was recently working on a CodeForce problem

So, I was using SymPy to solve this.

My code is :

from sympy import *

x,y = symbols("x,y", integer = True)
m,n = input().split(" ")

sol = solve([x**2 + y - int(n), y**2 + x - int(m)], [x, y])
print(sol)

What I wanted to do:

1. Filter only Positive and integer value from SymPy

Ex: If I put 14 28 in the terminal it will give me tons of result, but I just want it to show [(5, 3)]

Answer 1

I don't think that this is the intended way to solve the code force problem (I think you're just supposed to loop over the possible values for one of the variables).

I'll show how to make use of SymPy here anyway though. Your problem is a diophantine system of equations. Although SymPy has a diophantine solver it only works for individual equations rather than systems.

Usually the idea of using a CAS for something like this though is to symbolically find something like a general result that then helps you to write faster concrete numerical code. Here are your equations with m and n as arbitrary symbols:

In [62]: x, y, m, n = symbols('x, y, m, n')

In [63]: eqs = [x**2 + y - n, y**2 + x - m]

Using the polynomial resultant we can eliminate either x or y from this system to obtain a quartic polynomial for the remaining variable:

In [31]: py = resultant(eqs[0], eqs[1], x)

In [32]: py
Out[32]: 
 2        2        4    
m  - 2?m?y  - n + y  + y

While there is a quartic general formula that SymPy can use (if you use solve or roots here) it is too complicated to be useful for a problem like the one that you are describing. Instead though the rational root theorem tells us that an integer root for y must be a divisor of the constant term:

In [33]: py.coeff(y, 0)
Out[33]: 
 2    
m  - n

Therefore the possible values for y are:

In [64]: yvals = divisors(py.coeff(y, 0).subs({m:14, n:28}))

In [65]: yvals
Out[65]: [1, 2, 3, 4, 6, 7, 8, 12, 14, 21, 24, 28, 42, 56, 84, 168]

Since x is m - y**2 the corresponding values for x are:

In [66]: solve(eqs[1], x)
Out[66]: 
?     2?
?m - y ?

In [67]: xvals = [14 - yv**2 for yv in yvals]

In [68]: xvals
Out[68]: [13, 10, 5, -2, -22, -35, -50, -130, -182, -427, -562, -770, -1750, -3122, -7042, -28210]

The candidate solutions are then given by:

In [69]: candidates = [(xv, yv) for xv, yv in zip(xvals, yvals) if xv > 0]

In [70]: candidates
Out[70]: [(13, 1), (10, 2), (5, 3)]

From there you can test which values are solutions:

In [74]: eqsmn = [eq.subs({m:14, n:28}) for eq in eqs]

In [75]: [c for c in candidates if all(eq.subs(zip([x,y],c))==0 for eq in eqsmn)]
Out[75]: [(5, 3)]

The algorithmically minded will probably see from the above example how to make a much more efficient way of implementing the solver.