Largest prime gap under $2^{64}$

Solution 1:

With the new computations by Prime Gap Search project (Mersenne forum) it seems we now have the exact answer: the largest prime gap below $2^{64}$ has the size 1550. This gap follows the 20-digit prime $$p=18361375334787046697.$$ We have $\log_2 p \approx63.9933$.

See also T.R.Nicely's page First Occurrence Prime Gaps.

Solution 2:

A better upper bound is $10^9$. Starting at 1 (or $4\cdot10^{18}$, skipping the region checked by Oliveira e Silva's code), repeatedly add $10^9$ and find the previous prime. (I search for a probable prime and then prove primality with APR.) Repeat until you get a number in excess of the desired $2^{64}.$

The process might start: $1 \to 999999937 \to 1999999927 \to \cdots.$

I performed this check in parallel with a total of roughly 100 core-hours.

This could be extended to a smaller bound ($10^8$ with $10\times$ the effort, $10^7$ with $100\times$ the effort, etc.) if desired. Of course if you try with a number smaller than the largest gap in the region the program would loop forever (though it's not hard to check for this situation).

At some point it would just be more efficient to sieve the whole interval and get exact answers. Naively extrapolating Oliveira e Silva's Goldbach timings this would take about 2824 core-years, or about as long as a bound of length 4000. Since computers have gotten faster (albeit not much!) in the last four years, and since exact answers are much better, I certainly wouldn't recommend going lower than $10^4.$ I think even $10^6$ ($\approx$ 11 core-years) would take more effort than it's worth, unless you have access to serious computing power.