1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you want to solve for $x$ or $y$?. It makes a difference in the solution. $\endgroup$ – poetasis Jul 27 at 0:36
  • $\begingroup$ Thanks for the comment. I want to solve for both $x$ and $y$. $\endgroup$ – Matt Jul 27 at 0:37
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you! That's exactly what I needed! $\endgroup$ – Matt Jul 27 at 1:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.