# 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.

• True for $1<n<10^6$. Commented Aug 8, 2017 at 16:28
• true for $n<10^8$ (c++ source) Commented Aug 8, 2017 at 16:52
• This can be written as the existence (for all odd $n$) of a prime of the form $n^2+2k(n+k)$ for some $k\leq n$. Heuristically, one would expect a number of this size to be prime with probability $\frac {C'}{\ln(n^2)} = \frac C{\ln n}$ (the specific constant here is largely moot); since there are $n$ such numbers, the probability that none of them are prime is roughly $(1-\frac C{\ln n})^n$ $\approx e^{-Cn/\ln n}$, so the expected number of failures is finite (and the bound falls off pretty quickly). Commented Aug 8, 2017 at 17:25
• @StevenStadnicki ...of the form $n^2-2k(n-k)$ Commented Aug 8, 2017 at 17:34
• In any case the corresponding primes must be of the form $4m+1$ (Fermat) because the primes of the form $4m-1$ are not representable as a sum of two squares. Commented Aug 8, 2017 at 17:55

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.

• So there is probably no counterexample but probably very difficult to prove that?
– Lehs
Commented Aug 8, 2017 at 19:21
• Can we prove the result for almost every $n$? If not, let $R(x)$ denote the number of $n\leq x$ such that there exists $a,b\geq 0$ with $a+b=n$ and $a^2+b^2$ prime. Then the conjecture states that $R(x)=x$, and the infinitude of the primes of the form $a^2+b^2$ shows that $R(x)\rightarrow\infty$ as $x\rightarrow\infty$. What is the best lower bound we can show for $R(x)$? Commented Aug 9, 2017 at 0:22
• I suspect that since sieve methods will show that the number of such representations for $n$ is at most a constant times the expected number, your argument will already give $R(x) \gg x/\log x$. (PS: conjecturally $R(x) = \frac x2 + O(1)$.) Commented Aug 9, 2017 at 2:16

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

• It is clear that in $M_3$ there is a slip and it must be $M_3=(2n-2)^2+3^2$. I prefer to clarify this in a comment rather than edit. Commented Aug 9, 2017 at 15:57

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.