I wasn’t content with the existing estimates, so I built a probability model to estimate when we will find the remaining primes. Based on this model, there is a 50% probability that we will find one more prime before n=3.7 million, and two more primes before n=5.1 million. There is a 95% probability of finding one more before n=7.2 million, and two more before n=13 million. But if the model is reasonable, we may be here a very very long time. There is a 50% probability that we will get all 12 primes by n=2.9 x 10^13, and a 95% probability we will find all twelve by 1.9 x 10^23.

My approach started by finding a partial covering set for each of the remaining twelve “k” values. If you don’t yet understand covering sets, look at Team PrimeRib’s proof that 78557 is a Sierpinski Number. That proof shows that seven specific prime numbers “cover” all the possible values of 78557 x 2^n + 1. These prime divisors repeat in cycle of length 36. For the remaining twelve k-values I created partial coverings with a cycle length of 720 – there are twenty-eight primes that can contribute to such a cycle. Then I calculated the number of “holes” in each partial covering – the number of values in each sequence of 720 “n” values that is not divisible by one of the twenty-eight specific primes. The number of holes ranged from eight holes for k=22699 and k=67607 through forty-four holes for k=55459.

Next I undertook adjustments to the generic probability that a number is prime. The generic probability that “x” is prime is approximately 1/ln(x). For one of our Proth numbers, this is approximately 1/(ln(k)+n*ln(2)). But we can make three adjustments to this generic probability because we have special knowledge.

For the first adjustment, consider the twenty-eight specific primes and p=2. The generic probability includes the factor that “x” is not divisible by any of these twenty-nine specific primes as the product of (1-1/p) – this product is 0.144861. But we have special knowledge from the partial covering set that at least one of these numbers divides the Proth number unless n falls into one of the holes in the cycle of 720. So we can “replace” the factor of 0.144861 by (# of Holes)/720.

For the second adjustment, consider the primes not in the specific set. The generic probability counts each of these as “not dividing with probability (1-1/p) = (p-1)/p.” But look at the proof for 78557 again. The divisibility of primes cycles in a period of length (p-1) or a divisor of (p-1). If the period is length (p-1), the correct probability that p does not divide the Proth number is (p-2)/(p-1). If the cycle length is a divisor, the correct value is either (d-1)/d or it is “1.0”, depending on whether p ever divides the Proth numbers for that k. But averaged over all k values, the result is again (p-2)/(p-1). This adjustment ought to made for every prime that could divide a Proth number, replacing the (p-1)/p with (p-2)/(p-1). This adjustment factor converges to 0.992318.

For the third adjustment, consider the primes that divide “k.” If these primes are in the list of specific primes, we have already adjusted for them. Otherwise the generic probability (after the second adjustment) includes a factor of (p-2)/(p-1) that the Proth number is not divisible by p – but we know the correct probability is “1.0”, so we can make those corrections.

The net result of these adjustments is that the generic probability is reduced by a factor that ranges from 0.076114 for k=67607 to 0.418855 for k=55459. To finish, we need to accumulate these adjusted probabilities for values of n starting at 3 million.

Two more simple tricks and the model is complete. To accumulate these probabilities over large numbers of “n” values, we can integrate instead adding. The result of the addition or integration is actually the expected number of primes in the range. To calculate the probability of zero primes in a range with expected number “a”, we can use the Poisson approximation of exp(-a). Now we have all the tools to estimate the probability that a particular k value has zero – or more than zero – primes in a range of n values starting at 3 million. The estimates at the beginning of this message are built from combinations of these