26 August 2008

Predicting the next Mersenne prime

Robert at Casting Out Nines reports the new that the Great Internet Mersenne Prime Search claims to have found the 45th Mersenne prime, but they're waiting for verification before they report its identity. He invites guesses on the number of digits.

Here's my guess. A remark in Sloane's encyclopedia says the number of Mersenne primes up to exponent N is, conjecturally, about K log N for some constant K. (Here's a plot illustrating that.)

Let Nr denote the exponent of the rth Mersenne prime. The 44th Mersenne prime has exponent N44 = 32582657, so we have approximately

44 ~ K log 32582657

from which we get K ~ 2.5434. Thus the 45th Mersenne prime has exponent N45 satisfying approximately 45 ~ K log N45; thus N45 ~ 48276546. (Alternatively, we could have raised 32582657 to the 45/44 power, but it's not obvious why!) So the number of digits is approximately N45 log10 2 ~ 14532688; I'll take 14.5 million digits.

This method, it turns out, might show some sort of systematic bias. If I'd predicted Nr = (Nr-1)(r/(r-1)) with r = 2, 3, ..., 44, I would have had 16 underpredictions (the predicted exponent less than the true exponent) and 27 overpredictions. That's not quite statistically significant but it's not something you'd just neglect either. But this is just for fun -- if I were seriously trying to make a prediction I would have defined things more precisely, for one. (Oddly enough, since Mersenne primes get sparser as exponents get larger, the "most likely" single exponent is probably the single prime after N44 -- unless there's something that keeps them from clustering!) But if I were going to bet on this I'd also take into account the history of GIMPS; how long has it been since they've reported a prime, and how quickly does their search appear to move?

If you want to take a shot at that, be my guest. (I may regret what I've just unleashed.)

2 comments:

Anonymous said...

Can someone tell me why this matters?

Anonymous said...

Kimi, can you tell us why it has to "matter"?