# Determining thresholds based on value of variable

All variables here are integers.

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

I am trying to generate all $x,y$, given valid ranges $1\leq x\leq N$ and $-N\leq y\leq N$ intelligently.

Basically, given a selection of $x$ from 1 to $N$, I'd like to know the lower and upper integer bounds for $z$. Or, if it's easier, a selection of $y$ instead.

-

The first thing to note is that if $z$ is odd, then so is $x$ and vice versa because otherwise $z^2-x^2$ would be odd, and so not equal to $4y$ with $y\in\mathbb Z$. If both are even, then $z^2$ and $x^2$ are both divisible by 4 and so the equation has a unique solution. If both are odd, say $x=2n+1$ and $z=2m+1$, then $z^2-x^2=4(m^2-n^2+m-n)$ and the equation again has a unique solution.

Given some $x$ and the knowledge that $-N\leq y\leq N$, and letting $z\geq 0$, we can say though some real analysis that $z=\sqrt{x^2+4y}\leq x+\frac{2y}{x}$, so that $z\leq x+\frac{2N}{x}$. For the lower bound, if $x\leq \sqrt{N}$, then the argument of the square root can get less than $0$, so $z\geq 0$ is the best you can do. Otherwise, a simple linear bound is $\sqrt{x^2+4y}\geq x+\frac{4y}{x}$ for $0\leq y\leq x$ so that $z\geq x-\frac{4N}{x}$.

Computationally, you can use the simplicity of the solutions in $x$-$z$ space to enumerate the solutions: Given an $x$, start at $z=0$ or $1$ (or the other lower bound mentioned above) depending on whether $x$ is even or odd, solve for $y=\frac{1}{4}(z^2-x^2)$, and increase $z$ by twos until $y$ is greater than $N$. Doing this for $x=1$ to $N$ will give all possible solutions in the range you posed, although it may give extra solutions $y<-N$ if $x\geq\sqrt{N}$ as mentioned.

-

This is not an answer but a long comment.

First, observe your equation is equivalent to the equation $z^2 + (2y)^2 = (x + 2y)^2.$ Solutions of this latter equation are pathagorean triples and are well known. It follows that the complete list of solutions for your equation is

$$z = \pm k(n^2 - m^2)$$ $$2y = \pm k(2nm)$$ $$x + 2y = \pm k(n^2 +m^2)$$

where $n,m, k$ are arbitary positive integers such that n > m, i.e.

$$z = \pm k(n^2 - m^2)$$ $$y = \pm k(nm)$$ $$x= \pm k(n^2 +m^2) - \pm 2k(nm).$$

-
Wouldn't the last one be minus plus-or-minus k(2mn)? So how would I go about actually generating these triples in a systematic way, and how would I know the boundary conditions? – MyNameIsKhan Nov 26 '12 at 19:03