Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

All variables here are integers.


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.

share|cite|improve this question

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.

share|cite|improve this answer

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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