The previous post looked at tightly clustered primes. This post looks at the opposite, large gaps between primes.
Riecoin is a cryptocurrency that uses finding prime clusters as its proof of work task. Gapcoin uses finding prime gaps as its proof of work task.
There’s some nuance to defining prime gaps. It’s trivial to produce a gap of any size. For example, [n!, n! + n] is an interval of length n that contains no primes. It is more interesting to find gaps that are large relative to the size of the endpoints. The merit of a gap is the ratio of the gap length to the log of the initial number in the interval.
To be specific, suppose p and q are consecutive primes. The length of the gap between them is defined to be q − p and the merit of that gap is (q − p) / log p. For large p, the average gap between primes near p is log p and so the merit function measures how large the gap is relative to what you would expect for the size of p.
The following code will compute the merit function.
>>> from sympy import nextprime, log, N >>> merit = lambda p: (nextprime(p) - p)/log(p)
Gapcoin adjusts its mining difficulty by adjusting the minimum merit value the miner must search for. Gapcoin miners must find a prime p of the form
p = h × 2a + b
where h is the SHA256 hash of the previous block in the blockchain and b < 2a.
The prime gap with the largest known merit is [p, p + 8350] where
p = 293703234068022590158723766104419463425709075574811762098588798217895728858676728143227
The code
>>> N(merit(p))
shows that the merit is 41.94.
This record was found by the Gapcoin network. I don’t know the backstory, but I presume the mining task wasn’t to find a world record gap. Instead, the miner got lucky and found a much larger gap than necessary.