Natural numbers large enough can be written as $ab+ac+bc$ for some $a,b,c>0$

Question

Conjecture: Any integer $n>462$ can be written as $n=ab+ac+bc$, where $a,b,c\in\mathbb Z_+$.

Tested for all $n\leq 100,000$, but I would like to see a proof.

The exceptions seems to be $\{1,2,4,6,10,18,22,30,42,58,70,78,102,130,190,210,330,462\}$

---

It's funny, I played around with BigZ and found that every odd prime seemed to be on the form. I was going to post on that, but then I found that almost any number where on this form. And now it turns out that it depends on the Generalized Riemann Hypothesis.

Answer 1

In their paper On the representations of xy+yz+zx,xy+yz+zx, Exper. Math. 2000, 153-158, Borwein and Choi prove that only one other possible solution exists ($> 10^{11}$) and that cannot occur if we assume the Generalized Riemann Hypothesis.

This problem is closely connected to old problems on class numbers of imaginary quadratic fields, e.g. see the excerpt below from the Putnam collection by Kedlaya, Poonen, Vakil.

Answer 2

Not an answer, just a reduction to one particular class of cases.

Claim: If there is a prime $p<2\sqrt{n}$ such that $p\not\mid n$ and $-n$ is a square modulo $p$, then such $a,b,c$ exist.

When $n>1$ is odd, we have $(a,b,c)=\left(1,1,\frac{n-1}{2}\right)$.

When $n>4$ is divisible by $4$, we have $(a,b,c)=\left(2,2,\frac{n}{4}-1\right)$.

So we only need to solve for $n\equiv 2\pmod{4}$.

As JG pointed out, if $n+1$ is not prime, with factorization $n+1=uv$, $u,v>1$, then we get $(a,b,c)=(1,u-1,v-1)$.

So we've reduced to when $n+1\equiv 3\pmod{4}$ is a prime.

[I suppose that all these cases can be seen via Jaap's comment about seeking $c$ so that $n+c^2=rs$ with $r,s>c$. In the case $c=1$ give us the odd case or $n+1$ composite, the case $c=2$ gives the case $n$ divisible by $4$.]

We will proceed using Jaap's comment:

If there exists $c$ such that $n+c^2=rs$ for some $r,s>c$, then we can choose $(a,b,c)=(r-c,s-c,c)$.

Let $p$ be a prime relatively prime to $n$ such that $-n$ is a square modulo $p$.

Then $n+c^2$ is divisible by $p$ for some $\frac{p-1}{2}<c<p$.

If $d=\frac{n+c^2}{p}$, we want $d>c$ to ensure a solution.

So we want $$pc<n+c^2$$

But $c^2-pc+n=\left(c-\frac{p}{2}\right)^2+n-\frac{p^2}{4}$.

So if $p^2\leq 4n$ then this value is positive, and we get $d>c$ and hence $(a,b,c)=(p-c,d-c,c)$.

---

This explains why $462$ is a good candidate to fail - $462=2\cdot 3\cdot 7\cdot 11$, so $-462$ needs to not be square modulo $5,13,17,19,23,29,31,37,41$. Essentially, for large $n$ we need a lot of distinct prime factors.

It also explains why $n$ tends to be square-free in the examples.

If $p^2\mid n$ then $n+p^2=p^2\left(1+\frac{n}{p^2}\right)$ so if $p^2\mid n$ then $1+\frac{n}{p^2}\leq p$, and it must be prime. If it is not prime, then $n+p^2=(pa)(pb)$ where $ab=1+\frac{n}{p^2}$. That gives us that if $n$ has a square factor then $n=p^2(q-1)$ for some prime $q\leq p$, and there must be no solution to $ab+ac+bc=q-1$.

---

If $d\mid n$ then $d+\frac{n}{d}$ must not be factorizable as $ab$ with $a>1,b>d$, or otherwise, $n+d^2$ is factorizable as $(ad)(b)$.

But if $d+\frac{n}{d}\geq d^2$ this means that $d+\frac{n}{d}$ must be prime.

So, if $d\mid n$ and $d\leq \sqrt[3]{n}$, you must have $d+\frac{n}{d}$ prime.