# Any odd number is of form $a+b$ where $a^2+b^2$ is prime

This conjecture is tested for all odd natural numbers less than $10^8$:

If $n>1$ is an odd natural number, then there are natural numbers $a,b$ such that $n=a+b$ and $a^2+b^2\in\mathbb P$.

$\mathbb P$ is the set of prime numbers.

I wish help with counterexamples, heuristics or a proof.

Addendum: For odd $n$, $159<n<50,000$, there are $a,b\in\mathbb Z^+$ such that $n=a+b$ and both
$a^2+b^2$ and $a^2+(b+2)^2$ are primes.

As hinted by pisco125 in a comment, there is a weaker version of the conjecture:

Every odd number can be written $x+y$ where $x+iy$ is a Gaussian
prime.

Which give arise to a function:

$g:\mathbb P_G\to\mathbb O’$, given by $g(x+iy)=x+y$, where $\mathbb O’$ is the odd integers with $0,\pm 2$ included.

The weaker conjecture is then equivalent with that $g$ is onto.

The reason why the conjecture is weaker is that any prime of the form $p=4n-1$ is a Gaussian prime. The reason why $0,\pm 2$ must be added is that $\pm 1 \pm i$ is a Gaussian prime.

Here are some heuristics. As Hans Engler defines, let $k(n)$ be the number of pairs $(a,b)$ with $a<b$ for which $a+b=n$ and $a^2+b^2$ is prime. In other words,
$$k(n) = \#\{ 1\le a < \tfrac n2 \colon a^2 + (n-a)^2 = 2a^2 – 2an + n^2 \text{ is prime} \}.$$
Ignoring issues of uniformity in $n$, the Bateman–Horn conjecture predicts that the number of prime values of an irreducible polynomial $f(a)$ up to $x$ is asymptotic to
$$\frac x{\log x} \prod_p \bigg( 1-\frac1p \bigg)^{-1} \bigg( 1-\frac{\sigma(p)}p \bigg),$$
where $\log$ denotes the natural logarithm and
$$\sigma(p) = \#\{ 1\le t\le p\colon f(t) \equiv 0 \pmod p \}.$$

We now calculate $\sigma(p)$ for $f(a) = 2a^2 – 2an + n^2$.
Note that the discriminant of $f$ is $(-2n)^2 – 4\cdot2n^2 = -4n^2$. Therefore if $p$ does not divide $-4n^2$, the number of solutions is given by the Legendre symbol
$$\sigma(p) = 1 + \bigg (\frac{-4n^2}p\bigg) = 1 + \bigg (\frac{-1}p\bigg) = \begin{cases} 2, &\text{if } p\equiv1\pmod 4, \\ 0, &\text{if } p\equiv3\pmod 4. \end{cases}$$
Furthermore, we can check by hand that if $p=2$ then $\sigma(p)=0$, while if $p$ divides $n$ then $\sigma(p)=1$. Therefore our prediction becomes
$$k(n) \approx \frac{n/2}{\log(n/2)} \cdot 2 \prod_{\substack{p\equiv1\pmod 4 \\ p\nmid n}} \frac{p-2}{p-1} \prod_{\substack{p\equiv3\pmod 4 \\ p\nmid n}} \frac p{p-1}.$$
(We’re abusing notation: those two products don’t individually converge, but their product converges when the primes are taken in their natural order.)
In principle that constant could be cleverly evaluated to several decimal places. But for the purposes of experiment, perhaps it’s valuable to note that $k(n)$ should be approximately $n/\log n$, times some universal constant, times
$$\prod_{\substack{p\equiv1\pmod 4 \\ p\mid n}} \frac{p-1} {p-2}\prod_{\substack{p\equiv3\pmod 4 \\ p\mid n}} \frac {p-1}p;$$
and so the data can be normalized by that function of $n$ to test for consistency.