# Number of solution for $xy +yz + zx = N$

Is there a way to find number of "different" solutions to the equation $xy +yz + zx = N$, given the value of $N$.

Note: $x,y,z$ can have only non-negative values.

• This seems like a very interesting (and possibly very hard) question. The sequence begins $1, 3, 6, 7, 9, 9, 12, 9, 15, 12, 12, 15, 19, 9, 18, 18, 18, 15, 18, 15, 27, 18, 12, 21, 30, 12, 24, 22, 21, 21, 24, 21, 30, 18, 18, 30, 36, 9, 24, 30, 30$ for $N=0,1,\ldots,40$. – David Bevan Jun 14 '13 at 8:36
• It's tabulated at oeis.org/A067751 with the comment, "An upper bound on the number of solutions appears to be $9\sqrt n$." – Gerry Myerson Jun 14 '13 at 9:43
• If you insist on the variables being positive, you lose about $3d(N)$ solutions, but you get numbers related to class numbers of quadratic fields. See docserver.carma.newcastle.edu.au/212/2/98_119-Borwein-Choi.pdf – Gerry Myerson Jun 14 '13 at 9:51
• See also the discussion starting on page 291 of Mordell's book, Diophantine Equations, for the relation to class numbers. – Gerry Myerson Jun 14 '13 at 9:59
• A simple way to calculate this number for arbitrary N is to enumerate all 3-tuples $(x, y, z)$ with $x \leq y \leq z \leq N$, and checking if it is a solution, essentially bruteforcing the solution (there are some possible optimizations, for example: one can easily see that $x = 1, y = 1, z = N - 2$ will be a solution if $N > 2$, and likewise some other combinations can be skipped becuase they are never a solution). Of course, this is not very elegant, but in fact this does answer your question (with a definite "yes, there is a way"). – Ruben Mar 16 '14 at 6:28

## 5 Answers

The problem is difficult, as it is related to the determination of class numbers of quadratic number fields. See the references I have given in the comments.

equation:

$XY+XZ+YZ=N$

Solutions in integers can be written by expanding the number of factorization: $N=ab$

And using solutions of Pell's equation: $p^2-(4k^2+1)s^2=1$

$k$ -some integer which choose on our own.

Solutions can be written:

$X=ap^2+2(ak+b+a)ps+(2(a-2b)k+2b+a)s^2$

$Y=2(ak-b)ps+2(2ak^2+(a+2b)k+b)s^2$

$Z=bp^2-2(2b+a)kps+(4bk^2-2ak-b)s^2$

And more:

$X=-2bp^2+2(k(4b+a)+b)ps-2((4b+2a)k^2+(2b-a)k)s^2$

$Y=-(2b+a)p^2+2(k(4b+a)-b-a)ps-(8bk^2-(4b+2a)k+a)s^2$

$Z=bp^2-2(2b+a)kps+(4bk^2-2ak-b)s^2$

• Where does all this come from?! – vonbrand Mar 11 '14 at 14:42
• I do not understand? How? It is necessary to solve the equation. – individ Mar 11 '14 at 15:18

Perhaps these formulas for someone too complicated. Then equation:

$XY+XZ+YZ=N$

If we ask what ever number: $p$

That the following sum can always be factored: $p^2+N=ks$

Solutions can be written.

$X=p$

$Y=s-p$

$Z=k-p$

the equation: $XY+XZ+YZ=a(X+Y+Z)$

Solutions can be written using the solutions of Pell's equation:

$p^2-(k^2-k+1)s^2=a$

$k$ - This number can be any and defined by us.

Then the decision will be Met form:

$X=p^2+(k+1)ps$

$Y=p^2+(k-2)ps$

$Z=p^2+(1-2k)ps$

And more.

$X=(k+1)ps-(k^2-k+1)s^2$

$Y=(k-2)ps-(k^2-k+1)s^2$

$Z=(1-2k)ps-(k^2-k+1)s^2$

Here is a C# program that does the job in a pretty naive way. It eliminates some possibilities, then bruteforces all solutions. You can also use the Mathematica code provided on the OEIS page on this sequence (thank Gerry Myerson for this!).

using System;

class Program
{
static void Main(string[] args)
{
Console.Write("N = ");
int N = int.Parse(Console.ReadLine());
Console.WriteLine();

int u = 0, add = -1, n = 0, s = 0;
while (u < 2 * N) { u += (add += 2); n++; }
while (n <= N + 1)
{
if (canBeWrittenAsSumOfThreeSquares(u - 2 * N))
{
for (int x = 0; x <= n / 3; x++)
for (int y = x; y <= (n - x) / 2; y++)
{
int z = n - x - y;
if (x * y + y * z + z * x == N)
{
Console.Write(x + ", " + y + ", " + z + " ");
if (x != y && y != z && x != z) { Console.WriteLine("(6 permutations)"); s +=     6; }
else if (x == y && y == z) { Console.WriteLine("(1 permutation)"); s++; }
else { Console.WriteLine("(3 permutations)"); s += 3; }
}
}
}
u += (add += 2);
n++;
}
Console.WriteLine(s + " solutions found.");
Console.ReadKey(true);
}

static bool canBeWrittenAsSumOfThreeSquares(int n)
{
while (n % 4 == 0 && n > 0) n /= 4;
return n % 8 != 7;
}
}


The code uses the fact that $xy + yz + zx = \frac{(x + y + z)^2 - x^2 - y^2 - z^2}{2}$. When we have $xy + yz + zx = N$, we have $(x + y + z)^2 - x^2 - y^2 - z^2 = 2N$ and $(x + y + z)^2 - 2N = x^2 + y^2 + z^2$ a number can be written as a sum of three squares iff it is not of the form $4^k(8m + 7)$ see wikipedia article. So we simply check all $u \in \mathbb{N}$ so that $0 \leq u^2 - 2N \leq N^2$, and then iterate through all increasing ($x \leq y \leq z$) 3-tuples $(x, y, z)$, multyplying with the number of permutations that is possible (either 1, if all three components are the same, 3, when two components are the same and one different, or 6, when all the components are different).

I haven't used any advanced theorem (class numbers?), but I just wanted to illustrate that there is an approach that works for small $N$. I was able to calculate the amount of solutions for $N=4000$ in about one minute. This approach probably can be expanded to be more efficient.