# Finding all solutions of a quadratic Diophantine equation with two unknowns below a given bound

I have the quadratic Diophantine equation: $$2x^2-y^2-y=0$$ $$x < y$$ and I'm writing a computer program which requires finding all positive integer solutions to this equation for $$y\leq b$$, where $$b$$ is a bound which could potentially be very large.

So far, the only way I seem to be able to solve this is by iterating over all $$y\leq b$$, solving for x and checking the result, which can be very slow.

Is there a more efficient way to do this? I've read that quadratic Diophantine equations can be represented as two Pell like equations which can be solved more easily but I have not been able to find a clear explanation of this.

• Do you want to solve for $x$ or $y$?. It makes a difference in the solution. Jul 27, 2019 at 0:36
• Thanks for the comment. I want to solve for both $x$ and $y$. Jul 27, 2019 at 0:37

$$8x^2 - 4 y^2 - 4 y - 1 = -1$$ $$(2y+1)^2 - 8 x^2 = 1$$ $$w^2 - 8 x^2 = 1 \; ,$$ so that $$w$$ really is odd, then $$y = (w-1)/2$$

The first two are $$(w,x) = (1,0)$$ then $$(w,x) = (3,1)$$

After that, growth comes from $$(w,x) \mapsto (3w+8x, w + 3x )$$ over and over

w:  1  x:  0
w:  3  x:  1
w:  17  x:  6
w:  99  x:  35
w:  577  x:  204
w:  3363  x:  1189
w:  19601  x:  6930
w:  114243  x:  40391
w:  665857  x:  235416
w:  3880899  x:  1372105
w:  22619537  x:  7997214


but still followed by $$y = (w-1)/2$$ for each

If preferred, there are separate recurrences

$$w_{n+2} = 6 w_{n+1} - w_n \; , \;$$ $$x_{n+2} = 6 x_{n+1} - x_n \; . \;$$

• Thank you! That's exactly what I needed! Jul 27, 2019 at 1:00