# Unique Decomposition of Primes in Sums Of Higher Powers than $2$

Primes of the form $p=4k+1\;$ have a unique decomposition as sum of squares $p=a^2+b^2$ with $0<a<b\;$, due to Thue's Lemma.

What is known about sums of $n$ higher powers resulting in primes?

I tried $a^3+b^3+c^3$, asked Wolfram and found $3,17,29,43,73$, a sequence that I don't know (EDIT: thanks to Matthew: A007490). Interestingly, that $251$ has even $2$ decompositions, $1^3+5^3+5^3=2^3+3^3+6^3$.

Can anybody help here?

-
By the solution of Waring's Problem, for any exponent $e$ there is an $n=n(e)$ such that every positive integer is a sum of $n$ (positive) $e$-th powers. The case $e=3$ gets very interesting if we allow some of $a$, $b$, $c$ to be negative. – André Nicolas Jun 26 '12 at 22:10
$46747 = 30^3 +27^3 +4^3 = 31^3 +25^3 +11^3 = 36^3 + 4^3 +3^3$. – Matthew Conroy Jun 26 '12 at 22:59
I believe the next case with more than one decomposition is $1009 = 4^3 + 6^3 + 9^3 = 1^3 + 2^3 + 10^3$, and the first with three is $46747=11^3+25^3+31^3 = 4^3 + 27^3 + 30^3 = 3^3 + 4^3 + 36^3$. – Robert Israel Jun 26 '12 at 22:59
The most decompositions I have found are 6 each for $3380833$ and $5377373$ – Robert Israel Jun 26 '12 at 23:00
There are ${N \choose 3} \approx N^3/6$ triples of positive integers up to $N$, so the expected number of these whose sum of cubes is a given positive integer up to $N^3$ is approximately constant. Heuristically, we might use a Poisson distribution to model the number of decompositions. So there should be examples (increasingly rare as $k$ increases) with any number $k$ of decompositions. – Robert Israel Jun 26 '12 at 23:16

Any cube is congruent to $0$, $1$, or $-1$ modulo $9$. It follows that the sum of three cubes cannot be congruent to $4$ or $5$ modulo $9$. So we have a congruential restriction analogous to the case of two squares.
By Dirichlet's Theorem on primes in arithmetic progressions (or undoubtedly by much more elementary means) one can show that there are infinitely many primes congruent to $4$ modulo $9$, and also infinitely many primes congruent to $5$. Thus there are infinitely many primes that cannot be represented as the sum of three cubes.
About primes not congruent to $4$ or $5$ modulo $9$, one cannot say much. A long-standing conjecture is that every integer which is not congruent to $4$ or $5$ modulo $9$ is the sum of $3$ cubes. (Here negative cubes are allowed.) There has been a lot of computation on this problem.