# Prime as sum of three numbers whose product is a cube

Good evening! I am very new to this site. I would like to put the following materiel from Prof. Gandhi's note book and my observations. Of course it is little long with more questions. But, with good belief on this site, I am sending for good solutions/answers.

If we take other than primes $2$, $5$ and $11$, every prime can be written as $x + y + z$, where $x$, $y$ and $z$ are some positive numbers. Interestingly, $x \times y \times z = c^3$, where $c$ is again some positive number. Let us see the magic for primes $3$, $7,13,17,\ldots$ \begin{align} 3 = 1 + 1 + 1 &\Longrightarrow 1 \times 1 \times 1 = 1^3\\ 7 = 1 + 2 + 4 &\Longrightarrow 1 \times 2 \times 4 = 8 = 2^3\\ 13 = 1 + 3 + 9 &\Longrightarrow 1 \times 3 \times 9 = 3^3\\ 17 = 1 + 8 + 8 &\Longrightarrow 1 \times 8 \times 8 = 4^3 \end{align} Can you justify the above pattern? How to generalize the above statement either mathematically or by computer?

But, I observed that it is true for primes less than $9500$. Can your provide a computational algorithm to describe this?

Also, prove that, we conjecture that except $1, 2, 3, 5, 6, 7, 11, 13, 14, 15, 17, 22, 23$, every positive number can be written as a sum of four positive numbers and the product is again can be expressible in 4th power. Now, can we generalize this? Also, I want to know that, is there any such numbers can be expressible as some of $n$-integers with their product is again in $n$-th power?

Thank you so much.

edit

Concerning this cubic property :

Notice that this can be extended to hold for almost all squarefree positive integers $> 2$, not just the primes.

for instance : we know for the prime $7$ : $7=1+2+4$ so we also get $7A = 1A + 2A + 4A$ and $1A * 2A * 4A$ is simply equal to $8A^3$.

In fact this can be extended to all odd positive integers $>11$ if $25,121$ have a solution.

Hence I am intrested in this and I placed a bounty.

I edited the question because its to much for a comment and certainly not an answer.

Btw Im curious about this Ghandi person though info about that does not get the bounty naturally.

I would like to remind David Speyer's comment : Every prime that is $1 mod 3$ is of the form $a^ 2 +ab+b^ 2$ , so that covers half the primes immediately.

So that might be a line of attack.

mick

-
A further generalization would be that there is an integer $N_{k, m}$ such that for any prime $p\gt N_{k,m}$, there exist positive $x_1,\dots, x_k$ such that $x_1+\cdots+x_k=p$ and $x_1x_2\cdots x_k$ is a perfect $m$-th power. There is also no real reason to confine attention to primes. –  André Nicolas Jun 18 '12 at 15:39
For the original question we can choose $\{x^2,2xy,4y^2\}$ then the sum is $(x+y)^2+3y^2$ which gets a lot of (most?) primes $p=6k+1$. Or $\{x^2,4xy,2y^2\}$ then the sum is $(x+2y)-2y^2$ which gets most (all?) primes $p=8k\pm 1$. In general $\{x^2,2b^2xy,4by^2\}$, or $\{x^2,4b^2xy,2by^2\}$ or $\{x^2,2^cxy,2^dy^2\}$ give variants of $x^2\pm Ny^2$ which I thought might lead to a solution, but there are gaps. –  Zander Jun 18 '12 at 18:56
There is no reason to focus attention on primes. Let's say that $N$ is clean if we can find positive integers $(x,y,z)$ with $x+y+z=N$ and $xyz$ a cube. If $N$ is clean, so is every multiple of $N$. Now, $2^6=7+8+49$, $5^2=3+4+18$ and $11^2=1+45+75$ are all clean. So the conjecture is equivalent to the much more natural conjecture every sufficiently large integer is clean. –  David Speyer Jun 18 '12 at 19:58
We can pull a little more information out. $\gcd(x,y,z) = 1$, otherwise $p$ wouldn't be prime. Let $\displaystyle x=\prod_{i=1}^{j}p_{i}^{a_{i}}$, $\displaystyle y=\prod_{i=1}^{k}p_{i}^{b_{i}}$, and $\displaystyle z=\prod_{i=1}^{l}p_{i}^{c_{i}}$. Let $m=\max(j,k,l)$. Then $\displaystyle xyz=\prod_{i=1}^{m}p_{i}^{a_{i}+b_{i}+c_{i}}$. If $xyz$ is a cube, then for all $1 \le i \le m$, we know that $a_{i}+b_{i}+c_{i} \in 3\mathbb{Z}$. But we also know that $gcd(x,y,z)=1$, so either $a_{i}=0$, $b_{i}=0$, or $c_{i}=0$. Suppose $c_{i}=0$. Then $a_{i}+b_{i} \in 3\mathbb{Z}$, so $(a_{i},b_{i})$ is in –  Jackson Walters Jun 18 '12 at 21:33
Every prime that is $1 \mod 3$ is of the form $a^2+ab+b^2$, so that covers half the primes immediately. –  David Speyer Jun 18 '12 at 22:15

## 5 Answers

To add pessimism in finding such prime $p$ that cannot be written as sum of $3$ co-divisors of cube, I've drawn images:

Number of ways to write an integer number $p$ as the sum $x+y+z$, where $x\cdot y\cdot z=c^3$.

($\color{red}{\bf{red}}$ dots $-$ composite numbers, $\bf{black}$ dots $-$ prime numbers)

$$p\le 500$$

$$p\le 5\;000$$

$$p\le 50\;000$$

$$p\le 500\;000$$

$$p\le 5\;000\;000$$

Control points:
$p=486$ (composite): $1$ way: $486 = 162+162+162$;
$p=2048$ (composite): $2$ ways: $2048 = 128+720+1200 = 224+256+1568$;
$p=6656$ (composite): $3$ ways: $\small {6656 = 416+2340+3900 = 512+1536+4608 = 728+832+5096}$;
$p=7559$ (prime): $4$ ways: $\scriptsize{7559 = 9+50+7500 = 114+225+7220 = 135+1024+6400 = 722+2809+4028}$;
$p=26624$ (composite): $5$ ways;
$p=58757$ (prime): $10$ ways;
$p=80429$ (prime): $13$ ways;
$p=111611$ (prime): $15$ ways;
$...$

These images were made in style like here.
(Since I've seen images for Goldbach's conjecture, I lost any hope to find contradiction for it).

Method of search:

to build array $a[3N]$ for storing number of ways;

$a[p]$ is the number of ways to write $p$ as such sum; (initially, each $a[j]=0$);

for $c = 1 ... N$
$\quad$ create list of prime divisors of $c^3$;
$\quad$ (there is enough to know prime decomposition of $c$)
$\quad$ for each pair $x,y$ of divisors of $c^3$ to find $z=\dfrac{c^3}{xy}$;
$\quad$ if $z\in\mathbb{Z}$ and if $x\le y\le z$, then increase $a[x+y+z]$.

(if $c>N$, then sum of co-divisors of $c^3$ is greater than $3N$).

-

Two comments on positivity in David Speyer's method.

First, we can take $x,y > 0$ in $p = x^2 + x y + y^2,$ which we can do when $p \equiv 1 \pmod 3.$ Given $p = u^2 + u v + v^2,$ with $u>0$ but $v < 0.$ If $u+v > 0,$ we can use $p = (u+v)^2 + (u+v)(-v) + (-v)^2$ to get everything positive, as both $u+v, -v > 0.$ If $u+v <0,$ switch to $u^2 + u(-u-v)+ (-u-v)^2.$

Next, we get another good one with an indefinite form $$\color{blue}{x^2 + 4 x y + 2 y^2.}$$

Lemma: every (positive) prime $p \equiv \pm 1 \pmod 8$ can be written as $p = u^2 - 2 v^2$ with $u > 2v.$

Proof. Take the representation $p = u^2 - 2 v^2$ such that $v$ has the smallest possible positive value, with $u>0.$ Note that $u > v \sqrt 2,$ also $u$ is odd. We get a slightly different representation with $(u,-v).$ Next, we apply the generator of the automorphism group of $x^2 - 2 y^2$ to get another representation, $$(3u-4v, 2u-3v).$$

Now, if $2u - 3v \leq 0,$ by minimality of $|v|$ we also get $2u - 3 v \leq -v,$ so $2u \leq 2v$ and $u \leq v.$ This contradicts $u > v \sqrt 2.$

Therefore, $2u - 3 v > 0,$ and minimality again says $2u-3v > v.$ This gives us $2u>4v$ and $u > 2v.$

So we have $u > 2 v.$ Define $$x = u - 2 v, \; \; y = v.$$ Then $$p = x^2 + 4 x y + 2 y^2 = u^2 - 2 v^2,$$ with both $x,y > 0.$

EDIT, Thursday, August 21. The remaining primes are $5,11 \pmod 24.$ These are all represented by $2x^2 + 3 y^2,$ but the misfortune is that this does not give any cubes; furthermore, it appears that no $SL_2 \mathbb Z$-equivalent form has a product of the three coefficients a cube. So, the best i have come up with is $$14 x^2 + 36 xy + 147 y^2.$$ The good part is the cubes. there are two bad parts: it does represents only primes $5,11 \pmod {24},$ but the additional constraint is that the prime not be a quadratic residue $\bmod {17}.$ Furthermore, with a positivity constraint, as in the original problem, it represents only about half of those. So, all told, it gives only about one fourth of the remaining primes, such as $$197, 677, 1907, 1979, 2213 , 2237, 3083, 3803, 4091, 6011, 7349, 8429 , 10139 , 10781, 11213, \ldots$$

So, not bad but not great, about 13/16 of the primes so far.

EDIT, Friday, August 22.

It appears that all primes $p > 0$ with $(p|5) = 1$ and $(p|11) = 1$ are represented by $$x^2 + 25 xy + 5 y^2$$ with $x,y > 0.$ I think I have the proof; it starts with an elementary argument that the same can be accomplished for $x^2 + 23 xy- 19 y^2,$ then some fiddling with improper automorphs similar to the proof for $x^2 + 4 x y + 2 y^2$ but with more steps.

EEEDDDIIIITTTTTTT, Saturday, August 23:

THEOREM: given a prime $p > 30$ with $(p|5)=1$ and $(p|11)=1,$ we can write $p = x^2 + 25 x y + 5 y^2$ with positive integers $x,y.$

Take prime $p > 0$ and integers $s,t > 0$ with $$p = s^2 - 605 t^2.$$ Note that $s > t \sqrt {605} \approx 24.5967 t.$Then we can write $$p = x^2 + 23 x y - 19 y^2,$$ with $x = s - 23 t, \; \; y = 2 t,$ so that $x,y >0.$

Now, find the smallest positive integer $v$ such that there is another positive integer $u$ with $$p = u^2 + 23 u v - 19 v^2.$$

Lemma: given $p = x^2 + 23 x y - 19 y^2$ with $y < 0,$ then $y \leq -v.$

Proof: if $x < 0,$ we get a representation in positive integers $(-x,-y),$ so $-y \geq v.$ If $x > 0,$ note that $$x > \frac{\sqrt {605} + 23}{2} |y| \approx 23.798 |y|.$$ Therefore the new representation $(x + 23 y, -y)$ is again in positives and $-y \geq v.$

Corollary: if $p = x^2 + 23 x y - 19 y^2$ with $x <0, y >0,$ then $y \geq v.$

Back to the minimum $(u,v),$ both positive. Note $$u > \frac{\sqrt {605} - 23}{2} v \approx 0.798 v.$$

There is another representation, $$(4u-3v,5u-4v)$$ We know $5u-4v \neq 0$ as $p$ is not a square. If $5u-4v < 0,$ then $5u-4v \leq -v,$ thus $5u < 3 v.$ But this gives $u < 0.6 v,$ while in fact, $u > 0.798 v.$

Therefore, $5u-4v > 0,$ whereupon $5u - 4 v \geq v.$ Thus $5 u \geq 5 v$ and $u \geq v.$ Finally, as $u,v$ are relatively prime, they are not equal unless both are actually $1,$ giving the prime $5.$ Thus, for $p > 5,$ we get $u > v.$

Finally, finally, finally, we can write $$\color{blue}{ p = x^2 + 25 x y + 5 y^2}$$ with $$x = u - v, y = v$$ both positive.

-
If it is a quadratic residue modulo $5$ and $17$, then $9x^2+25xy+15y^2$ does the job, so I can cover half your remaining primes. Moreover, this one has positive discriminant, so I am cautiously optimistic about positivity. –  David Speyer Aug 22 '14 at 16:50
@DavidSpeyer, thanks. I will see what I can do with positivity and $9 x^2 + 25 xy + 15 y^2.$ At a minimum I can have the computer compare all positive primes represented to those represented with $x,y > 0.$ I see, it is the principal form of discriminant 85, $\langle 1,9,-1 \rangle,$ the other form and genus is $\langle 3,7,-3 \rangle,$ –  Will Jagy Aug 22 '14 at 17:36
Basically, my thinking is that, in positive discriminant, once we have one way of representing the prime, we can use a solution to Pell's eqn to write down infinitely many more. (In this case, the fundamental unit is $(9+\sqrt{85})/2$.) My intuition is that, if we write down a formula for these infinitely many solutions as a function of the first solution, it will be clear that some of them are positive. But I haven't done the work yet. –  David Speyer Aug 22 '14 at 18:35
@DavidSpeyer, I see what you mean. However, what i am getting is that all eligible primes can, apparently, be written $p=x^2 + 9 xy-y^2$ with $x,y>0,$ but only about one in five of those can be written as $p = 9 x^2 + 25 xy + 15 y^2$ with $x,y>0.$ From my lowbrow viewpoint, the trouble with the infinite set of solutions is that the generator of the automorphism group of $9 x^2 + 25 xy + 15 y^2$ will have minus signs in unfortunate places. –  Will Jagy Aug 22 '14 at 19:00
Ah, that makes sense. $9 x^2 + 25 xy + 15 y^2 = p$ is a hyperbola both of whose axes run through the $2$nd and $4$th quadrants. The integer points on this hyperbola are spaced exponentially apart. So there is only a finite section of the hyperbola in the first quadrant, and it might or not have any integer points. I screwed up the sign the first time I tried to visualize this, so I thought there was an infinite portion of the hyperbola in the $1$st quadrant. This is discouraging for the version of the question with positive cubes. That's the advantage of actually doing the work! Thanks! –  David Speyer Aug 22 '14 at 19:18

Here is an attempt that doesn't quite work. In this post, $\left( \frac{a}{p} \right)$ is the quadratic residue symbol.

If $\left( \frac{-3}{p} \right) = 1$, then $p$ is of the form $x^2+xy+y^2$.

If $\left( \frac{85}{p} \right) = 1$, then $p$ is either of the form $9 x^2 + 25 xy + 15 y^2$ or $3 x^2 + 25 xy + 45 y^2$.

If $\left( \frac{-255}{p} \right) = 1$, then $p$ is of one of the forms $x^2+xy+64 y^2$, $2 x^2 + xy + 32 y^2$, $4 x^2 + xy + 16 y^2$, $8 x^2 + xy + 8 y^2$, $3 x^2 + 3 xy + 22 y^2$, $5 x^2 + 5 xy + 14 y^2$, $6 x^2 + 3 xy + 11 y^2$ or $7 x^2 + 5 xy + 11 y^2$.

Now, one of the three quadratic residues must be $1$, since $\left( \frac{-255}{p} \right) = \left( \frac{-3}{p} \right)\left( \frac{85}{p} \right)$. And for a lot of the quadratic forms above, we win: $(x^2)(xy)(y^2)$, $(9 x^2)(25 xy)(15 y^2)$, $(3 x^2)(25 xy)(45 y^2)$, $(x^2)(xy)(64 y^2)$, $(2 x^2)(xy)(32 y^2)$, $(4 x^2)(xy)(16 y^2)$ and $(8 x^2)(xy)(8 y^2)$ are all cubes. Unfortunately, the last $4$ quadratic forms of discriminant $-255$ don't work when written in reduced form. I haven't yet done a serious search to see whether some change of basis might put them into the form $a x^2 + bxy + c y^2$, with $abc$ a cube.

Also, we don't know what the signs of $x$ and $y$ are, so this doesn't necessarily get us three positive integers whose product is a cube.

Still, I am optimistic that we might be able to find enough quadratic forms of the form $a x^2 + bxy + c y^2$, with $abc=1$, to cover all the primes, at least if we ignore the sign issue.

-
if $p = x^2 + x y + y^2$ with $x>0$ but $y<0,$ and $x+y > 0,$ we also have $p = (x+y)^2 + (x+y)(-y) + (-y)^2$ with both positive. If $x+y < 0,$ then $p = x^2 + x(-x-y) + (-x-y)^2$ –  Will Jagy Aug 20 '14 at 19:00
Nair arxiv.org/abs/math/0408107v1 also shows (in Theorem 3) that if $n=x^2+xy+y^2$ for any $x,y$, then $n=a^2+ab+b^2$ with both $a$ and $b$ non-negative. There might be other useful tidbits in that paper towards this question. –  Kieren MacMillan Aug 22 '14 at 20:29
Took me a while, but $x^2 + 25 x y + 5 y^2$ works for $p > 30$ residue mod 5 and mod 11. –  Will Jagy Aug 23 '14 at 21:30

I wrote a small script in MATLAB and verified your claim for all the primes less than $150,000$. Only $2,5,11$ do not satisfy your claim. For many of the primes, there are multiple ways to write it as a sum of three number such that its product is a cube. My script just looks for the first occurrence of such triplets for each prime.

Here is a .txt file with the "first" set of triplets for primes less than $150,000$.

-
Is it me, or does that link not work? I do have Dropbox, but I cannot access your file. –  TMM Jun 18 '12 at 22:58
@TMM Oops... I have fixed it now. Can you kindly let me know if you can access the file now? –  user17762 Jun 18 '12 at 23:06
Thanks, yes it works now. –  TMM Jun 18 '12 at 23:12
I wrote some Mathematica code to compute the number of triples satisfying the property for a given $n$, with the following caveat. Suppose $(x,y,z)$ is a 3-tuple satisfying the property. Any permutation of $(x,y,z)$ also satisfies the property. Say $(x,y,z) \sim (x',y',z')$ if $(x',y',z')$ is a permutation of $(x,y,z)$. Then let $T_{n}$ be the number of such equivalence classes. Here's a plot of $T_{n}$ for $1 \le n \le 200$. Note: There are no solutions for $n= 44$ or $176$. picasaweb.google.com/lh/photo/… –  Jackson Walters Jun 19 '12 at 20:38
Notice that $176$ is a multiple of $44$ ! –  mick Aug 16 '14 at 22:18

I wrote the following JavaScript which is designed to run in Windows Script host:

• isprime(n) - determine whether a number is prime via brute force method
• showmagic(f, txt) - writes a line to both screen and text file
• findmagic(f, n) - detects and writes the magic for a given prime
• main - tests the first 500 numbers

Save the script to a JavaScript file, say magic.js and invoke cscript magic.js from the command prompt to execute the script using the console version of the Windows Script Host. Because it's written in JavaScript, the script gets exponentially slower to run if you set it to test the first 10000 numbers.

function isprime(n) {
if (n < 2) return false;
for (var i=2; i*i<=n; i++)
if (n % i === 0) return false;
return true;
}

function showmagic(f, txt) {
f.WriteLine(txt);
WScript.Echo(txt);
}

function findmagic(f, n) {
for (var i=1; i<=n-2; i++) {
for (var j=1; j<=n-1-i; j++) {
var k=n-i-j;
var c3=i*j*k;
for (var c=1; c*c*c<=c3; c++) {
if (c*c*c === c3) {
showmagic(f, n + "=" + i + "+" + j + "+" + k + " ; " + i + "*" + j + "*" + k + "=" + c + "^3");
return;
}
}
}
}
showmagic(f, n + "=no magic");
}

var fso = new ActiveXObject("Scripting.FileSystemObject");
var f = fso.CreateTextFile("magic.txt", true);
for (var n=1; n<=500; n++)
if (isprime(n))
findmagic(f, n);
f.Close();

-
Does this add anything over the two-year-old answer which provides the results of such a calculation for the first 13K or so primes? The other answer doesn't show its code, but this is a very straightforward approach (and inefficient in a few spots - your method for finding out whether c3 is a cube is much slower than it could be). –  Steven Stadnicki Aug 19 '14 at 14:59