# Helper Me Speed Up Diophantine Solution?

Hi Folks.

Came across this question on Codewars, and I wasn’t even able to submit with a “this took longer than 12sec to run” for their submission test suite.

In mathematics, a Diophantine equation is a polynomial equation, usually with two or more unknowns, such that only the integer solutions are sought or studied.

In this kata we want to find all integers `x, y` ( `x >= 0, y >= 0` ) solutions of a diophantine equation of the form:

#### x^2 - 4 * y^2 = n

(where the unknowns are `x` and `y` , and `n` is a given positive number) in decreasing order of the positive xi.

If there is no solution return `[]` or `"[]" or ""` . (See “RUN SAMPLE TESTS” for examples of returns).

Here is my current solution using some horribly written recursion D:. It is MUCH more performant than my first few renditions, but still no where near fast enough to submit to codewars apparently. Can anyone help me understand why this is still slow?

``````
defmodule Dioph do

@eq "x2 - 4 * y2 = n"
@eq_terms_of_x "x = sqrt(n + (4 * y^2))"
@eq_terms_of_y " y = sqrt((-1 * (n - x^2))/4)"

def solve(n) do
k = round(n/2 + 1)
equation(n, k, []) |> Enum.reverse
end

def equation(_, 0, acc), do: acc
def equation(n, val, acc) do
x = val
right_side = (-1 * (n - :math.pow(x, 2))/4)
y = if right_side < 0.00, do: -1.00, else: :math.sqrt(right_side)
if is_valid_result?({x, y}), do: equation(n, val-1, [{round(x), round(y)}| acc]), else: equation(n, val-1, acc)
end

def is_valid_result?({x, y}) do
round(x) == x && x != -1 && round(y) == y && y != -1
end

end
``````

The problem with a “count down by one” solution like this is that the solution is very sparse relative to the input number - for instance, with `n=200_000_000`:

``````iex(6)> Dioph.solve(200000000)
[
{100000001, 50000000},
{25000002, 12499999},
{12500004, 6249998},
{6250008, 3124996},
{5000010, 2499995},
{3125016, 1562492},
{2500020, 1249990},
{1562532, 781234},
{1250040, 624980},
{1000050, 499975},
{781314, 390593},
{625080, 312460},
{500100, 249950},
{312660, 156170},
{250200, 124900},
{200250, 99875},
{156570, 77965},
{125400, 62300},
{100500, 49750},
{63300, 30850},
{51000, 24500},
{41250, 19375},
{32850, 14825},
{27000, 11500},
{22500, 8750},
{16500, 4250},
{15000, 2500},
{14250, 875}
]
``````

That’s a LONG way to count to get a handful of matches.

Brute-force is not going to perform well on this solution, but there’s a mathematical insight that can help skip past most of those 200 million choices:

``````x^2 - 4 * y^2 = (x - 2 * y) * (x + 2 * y)
``````

so both `x - 2 * y` and `x + 2 * y` have to be factors of `n`.

2 Likes