This is only based on empirical testing, but it seems like if you select a random $a^2$ and a random $b$ in a comparable range, you'll find that $a^2+b^2$ is significantly (by a margin of 25-30%) more likely to be prime than $a^2+b$. I assume there's a good number-theoretical reason for this, but it doesn't jump out at me, aside from karmic balance for the fact that $a^2-b^2$ is almost never prime.

  • 1
    $\begingroup$ It may just be the size of numbers you've tried, or it could have something to do with this, or it could be one of those questions in number theory which, though sounding simple enough to ask in primary school, remains intractable to the experts. $\endgroup$ – J.G. Sep 7 '19 at 9:45
  • 2
    $\begingroup$ Are the ranges of $a$ and $b$ the same? e.g., $0 < a < 100$ and $0 < b < 100$. Do you require $a > b$ or $a < b$? Have you looked at negative $b$? If your program does not consider negative numbers like $-89$ to be prime, then of course it will find that $a^2 + b^2$ is more likely to be prime that $a^2 + b$. For example, $a = 2$, $b = -7$; then $2^2 + (-7)^2 = 53$, but $2^2 + (-7) = 4 - 7 = -3$, which is supposedly not prime according to some programs. $\endgroup$ – Robert Soupe Sep 7 '19 at 16:49

Taking a random $a$ and $b$, the probability that $a^2+b^2$ is a multiple of $3$ is about $1/9$, since this happens only if $a$ and $b$ are both multiples of $3$. But the probability of $a^2+b$ being divisible by $3$ is about $1/3$, since no matter what $a$ is there is a roughly $1/3$ chance that $b\equiv -a^2\pmod 3$.

You will get a similar effect for any prime $p\equiv 3\pmod 4$, since for these primes $-1$ is not a quadratic residue, which implies there is no solution to $a^2+b^2\equiv 0\pmod p$ except $a\equiv 0,b\equiv 0$.


Say $1\leq a, b\leq N$, then $$ a^2+b\leq N^2+N\qquad\text{and}\qquad a^2+b^2\leq2N^2. $$ But while every prime $p$ is of the form $a^2+b$ (just take $a=1$, $b=p-1$) only those congruent to $1$ modulo $p$ are of the form $a^2+b^2$.

Thus by the prime number theorem (which says that there are about $x/\log x$ primes $\leq x$) the probability to hit a prime for random values of $a^2+b$ is $$ p_1=\frac{\log(N^2+N)}{N^2+N}=\frac{\log(N)+\log(N+1)}{N(N+1)} $$ while the probability of hitting a prime of the form $a^2+b^2$ is $$ p_2=\frac12\frac{\log(2N^2)}{2N^2}=\frac12\frac{\log(2)+2\log(N)}{2N^2} $$ where the factor $\frac12$ is there because the primes $\equiv1\bmod4$ have density $\frac12$.

Note that $p_1>p_2$.

  • $\begingroup$ Surely $p_1>p_2$ is the wrong way around to explain this effect? $\endgroup$ – Especially Lime Sep 7 '19 at 20:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.