Conjecture: All but 21 non-square integers are the sum of a square and a prime

This is Hardy and Littlewood's Conjecture $H$. It says that this sequence $a(n)= 10,34,58,85,\ldots$ is finite and that the number of representations of $n$ as the sum of a prime and a square is asymptotically $$ \frac{\sqrt{n}}{\log (n)} \cdot \prod_{p > 2}\left( 1 - \frac{(n / p)}{p - 1}\right)$$

where $(n / p)$ is the Legendre symbol.

References: Mikawa, Narkiewicz, Wang

The conjecture is tested up to $10^{11}$ so far, i.e., it is known that $a(22) > 10^{11}$, if it exists.

I found it interesting that this has been verified only up to $10^{11}$, so I wrote a small(ish) program veryifying the conjecture up to $10^{11}$ in just 400 seconds, and up to $1.6 \cdot 10^{13}$ in under one day. At that size it checks 1 billion numbers in about 5 seconds on a single three year old, not top-of-the-range computer.

The algorithm that I used:

Create a bitmap representing odd primes. Bit #i in that bitmap is set if 2i+1 is not a prime, and cleared if 2i+1 is a prime. This is stored as an array of 64 bit integers, so 64 potential primes can be processed in constant time. Increase the size of the bitmap whenever more primes are needed, since that number is hard to product.

Choose an integer w, and then examine whether the integers in [kw, (k+1)w) contain any counter examples to the conjecture, for k = 0, 1, 2 etc. Since all primes other than 2 are odd, we examine even integers and odd integers separately. (Even integers cannot be the sum of an even square and odd prime obviously, and odd integers cannot be the sum of an odd square and an odd prime).

To do this, we create a bitmap representing either the even or the odd integers in the range, and set a bit in the bitmap for each integer that might be a counterexample, and clear the bit if that integer is not a counterexample. Bit #i either represents kw + 2i, or kw + 2i + 1. We let S = largest integer such that $S^2 < (k+1)w$.

Initially all bits are set. Then we let s be the largest even/odd integer <= S, and clear the bit for $s^2$ (squares are excluded) and $s^2+2$ (sum of square and prime), plus we examine s-2, s-4 etc as well as long as their square is in the range.

Then we start with s = largest odd / even integer <= S. We can then use the bitmap of primes to very efficiently remove all sums $s^2 + p$ from the bitmap of potential counterexamples, for 64 integers at a time. Then we proceed with s-2, s-4, s-6 etc. until there are no counterexamples left or if the next s would be negative. And that's basically it; if you choose w as a multiple of 128 (to keep bit operations simple) and not too large (should fit into the first level cache of the computer, I picked something around 200,000), then this will run at a speed of a billion integers tested in a few seconds.

If you want to go further, there are two optimisations that I didn't bother to implement. First optimisation: For the first say 100 squares, most 64 bit words will contain one or more bits representing counter examples, but at some point these words get rare. At that point it will be faster to keep track of which 64 bit words represent any counter examples, and only inspect the primes for those words. This is especially beneficial when there is only a dozen or so counter examples left. My estimate is that this should make the algorithm 3 times faster.

The second optimisation is much more involved. As the algorithm proceeds, you can see that it consistently uses all the primes, and each one exactly once (for example if you examine integers around $10^{12}$, even squares are about 4 million apart, so the same primes are not reused). This means that these primes will not be cached but must be read from RAM each time, which is the worst thing we can do.

To avoid this, we need to change the order in which we examine numbers so that the same primes will be used repeatedly. We take w much smaller. Then we examine integers in a range ($s^2 + kw$, $s^2 + (k+1)w$ for k = 0, 1, 2, etc. and $s^2$ being consecutive squares. We skip ranges that would be covered by a larger s. The primes that are examined will be about kw to (k+1)w, then (4s + kw) to (4s + (k+1)w etc. When we examine the range ($(s+2)^2 + kw$ to $(s+2)^2 + (k+1)w$) we examine primes in the same range. If we keep w small enough that all these primes fit into some cache, the time to read them will be much faster. This could be an improvement from 3 to 10 times.

This also makes it worthwhile using multiple cores on a processor, making another substantial improvement possible with a much more expensive computer.

Now there is a HUGE problem with all of this: I haven't actually verified anything. I wrote a program that printed the exceptions that were suggested, and then printed whenever it didn't find more exceptions. However, to make sure that it actually did anything meaningful, someone would have to verify the source code very, very carefully to make sure that the output of the program actually verifies anything. And with some paranoia, you'd have to verify either the compiler or the compiled code.

For this particular problem, it is impossible to output anything that demonstrates the verification of the conjecture is correct. (Of course I could print how each number up to 16 trillions is the sum of a square and a prime, but that's practically impossible to verify).

PS. It seems that 78526384 might be the largest integer which is not a sure of a cube and a prime. Finding the largest integer which is not the sum of a fourth power and a prime turns out to be very difficult: First, the numbers involved are obviously a lot larger, because fourth powers are much more rare than squares or cubes. But there is another problem: It is always the case that a^4 modulo 10 = 1 or 6, except when a = 10 modulo 0 or 5. So if n = 1 modulo 10 or 6 modulo 10, then of the 5 even or odd fourth powers that we could subtract from n, four lead to a result ending in 0 or 5. Which makes it very much rarer that the difference is a prime.