0
$\begingroup$

$$t=x^2+4y$$

How do I generate all $x,y$ where $t$ is a perfect square greater than or equal to zero, given valid range $-N\leq x,y\leq N$?

All variables here are integers.

1 Answers 1

1

Since you want $t$ to be a perfect square, say $z^2$, we need $$x,y \in \{-N,-N+1,\ldots,0,\ldots,1,N-1,N\}$$ such that $x^2 + 4y = z^2$. Note that $z^2 \in \{0,1,2,\ldots,N^2 + 4N\}$ i.e. $z \in \{0,1,2,\ldots,N+1\}$. Note that $x$ and $z$ are of the same parity. Hence, choose any $$x \in \{-N,-N+1,\ldots,0,\ldots,1,N-1,N\}$$ For this $x$ choose $z \in \{0,1,2,\ldots,N+1\}$ having the same parity as $x$ such that $\vert z^2 - x^2 \vert \leq 4N$. Set $$y = \dfrac{z^2 - x^2}4$$

  • 0
    how do you get that z is bound by N+1? z^2=n^2+4n has solution z = +/- sqrt(n)sqrt(n+4)2012-11-25
  • 0
    Note that $(N+2)^2=N^2+4N+4$.2012-11-25