finding the number of integral solutions How can we find the number of integral solutions for the equation $xy + yz +zx = n$?
I tried using $3$ for loops for a given $n$ but for large $n$, say $\gt1000$, it takes a lot of time. Is there any efficient method? Thanks.
 A: There may be more subtle number-theoretic improvements to be made, but the most immediate improvement from $O(n^3)$ to $O(n^2)$ would be to have only two loops, say for $x$ and $y$, solve for $z$ and check whether $z$ is an integer, i.e. whether $x+y$ divides $n-xy$.
A: Since
$$xy+yz+zx=n\Leftrightarrow(x+z)(y+z)=n+z^2$$
for each $n$ and $z$, each factorizations of $n+z^2$ gives a solution.
For $n=1$ and $z=1$, we get $(x+1)(y+1)=2$
$$
\begin{array}{c|c|c|c}
x+1&y+1&x&y\\
\hline\\
-2&-1&-3&-2\\
1&2&0&1
\end{array}
$$
For $n=1$ and $z=2$, we get $(x+2)(y+2)=5$
$$
\begin{array}{c|c|c|c}
x+2&y+2&x&y\\
\hline\\
-5&-1&-3&-2\\
1&5&-1&3
\end{array}
$$
For $n=5$ and $z=1$, we get $(x+1)(y+1)=6$
$$
\begin{array}{c|c|c|c}
x+1&y+1&x&y\\
\hline\\
-6&-1&-7&-2\\
-3&-2&-4&-3\\
1&6&0&5\\
2&3&1&2
\end{array}
$$
Positive solutions
To find only positive solutions, we need consider only $(z+1)^2\le z^2+n$; i.e. $2z+1\le n$, and look only for factorizations of $z^2+n$ in which both factors are greater than $z$. To reduce duplications, only consider $3z^2\ge n$ and factorizations where neither factor is greater than $2z$.
Thus, consider only $\sqrt{n/3}\le z\le(n-1)/2$ and factors $(x+z)(y+z)=n+z^2$ in $[z+1,2z]$.
