1
$\begingroup$

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.

  • 3
    the values are these for given n http://oeis.org/A0677522012-11-10

2 Answers 2

2

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

1

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