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

Question

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.

Answer 1

$$ 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 \; . \; $$