# Generating valid x and y that result in perfect squares

$$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 Answer

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$$

-
how do you get that z is bound by N+1? z^2=n^2+4n has solution z = +/- sqrt(n)sqrt(n+4) –  MyNameIsKhan Nov 25 '12 at 0:44
Note that $(N+2)^2=N^2+4N+4$. –  anonymous Nov 25 '12 at 0:49