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

Question

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.

Answer 1

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.

Answer 2

One equivalent way to formulate this conjecture is also the following:

For each natural number $n$ we have: $ \displaystyle 0 = \prod_{\underset{\gcd(a,b)=1}{2n+1=a+b}} (\Omega(a^2+b^2)-1)$

This is equivalent as to say that the polynomial $\displaystyle f_n(t) = \prod_{\underset{\gcd(a,b)=1}{2n+1=a+b}} (t-\Omega(a^2+b^2))$ has zero $1$.

where $\Omega$ counts the prime divisors with multiplicity.

Answer 3

COMMENT.-This is another way, maybe interesting for some people, of stating the same problem.

Given an odd natural number, $2n + 1$, there are $n$ different ways to express it as the sum of two natural $$2n+1=(2n-k)+(k+1);\space k=1,2,....,n$$ Then the problem can be stated as follows equivalently: $$\text{ For all natural 2n+1 greater than 1}\text{ at least one of the n numbers}\\\begin{cases}M_1=4n^2+1\\M_2=(2n-1)^2+2^2\\M_3=(2n-3)^2+3^3\\...........\\...........\\M_n=(n+1)^2+n^2\end{cases}\\ \text{ is a prime}$$

NOTE.- It is known that such a prime (if it exists) is necessarily of the form $p=4m+1$. Besides each $M_k$ has a factorization of the form $$M_k=\prod p_i^{\alpha_i}\prod q_j^{2\beta_j}$$ where $\alpha_i,\space \beta_j$ are non-negative integers,the primes $p_i$ and $q_j$ being of the form $4m+1$ and $4m-1$ respectively.

While larger 2n + 1 is, more likely to exist such a prime number. It would seem that the conjecture is true