Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

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|improve this answer
add comment

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|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? –  AgainstASicilian Nov 26 '12 at 19:03
add comment

Your Answer

 
discard

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.