Tag Archives: mersenne prime

It’s official: They’re prime

The numbers believed to be the 45th and 46th Mersenne primes have been proven to be prime. The 45th Mersenne prime is 2^{37156667} -1 and the 46th is 2^{43112609} - 1.Full text of these numbers is here and here.

Of course what you are really wanting to know is how my spreadsheet models worked out for predicting the number of digits in these primes. First, the data:

  • Number of digits actually in M_{45}: 11,185,272
  • Number of digits actually in M_{46}: 12,978,189

My exponential model (d = 0.5867 e^{0.3897 n}) was, unsurprisingly, way off — predicting a digit count of over 24.2 million for M_{45} and over 35.8 million for M_{46}. But the sixth-degree polynomial — printed on the scatterplot at the post linked to above — was… well, see for yourself:

  • Number of digits predicted by 6th-degree polynomial model for M_{45}: 11,819,349
  • Number of digits predicted by 6th-degree polynomial model for M_{46}: 13,056,236

So my model was off by 634,077 digits — about 6% error — for M_{45}. But the difference was only  78,047 digits for M_{46}, which is only about 0.6% error. That’s not too bad, if you asked me.

There’s only one piece of bad news that prevents me from publishing this amazing digit-count predicting device, and you can spot it in the graph of the model:

So evidently the number of digits in M_{n} will max out around M_{49} and then the digit count will begin to decrease, until somebody discovers M_{55}, which will actually have no digits whatsoever. Um… no.

1 Comment

Filed under Crypto, Geekhood, Math

Estimating the digits in a Mersenne prime — for dummies

At the end of this post, I made a totally naive guess that the recently discovered candidate to be the M_{45}, the 45th Mersenne prime, would have 10.5 million digits. There was absolutely no systematic basis for that guess, but I did suggest having an office pool for the number of digits, so what I lack in mathematical sophistication is made up for by my instinct for good nerd party games. On the other hand, Isabel at God Plays Dice predicted 14.5 million digits based on a number theoretic argument. Since I am merely a wannabe number theorist, I can’t compete with that sort of thing. But I can make up a mean Excel spreadsheet, so I figured I’d do a little data plotting and see what happened.

If you make a plot of the number of digits in M_n, the nth Mersenne prime, going all the way back to antiquity, here’s what you get:

The horizontal axis is n and the vertical axis is the number of digits in M_n.

Admit it — one look at this plot and you’re itching to add some trendlines. Here’s what you get when you add both an exponential trendline (perhaps the obvious choice given the shape) and a 6th-degree polynomial:

The exponential one has a higher R^2 value, but that’s perhaps misleading because of the really good fit for all those low-digit Mersenne primes that happened prior to around M_{30}. We’ll take that issue up in a moment. But for now, let’s put those trendline equations to work. The exponential trendline would predict that M_{45} would have a digit count of

0.5867 e^{0.3897 \times 45} = 0.5867 e^{17.5365} \approx 24,233,786

which is obviously rather a lot more than either my prediction or Isabel’s; and if you put in x=45 into the 6th-degree polynomial, you get a digit count of 11819349, which is in the ballpark of both my rough estimate and Isabel’s estimate.

It doesn’t make much sense, though, to include all Mersenne primes, since Mersenne primes didn’t even cross the 100-digit mark until M_{13} in 1952. A more accurate idea — if you can call this kind of reasoning accurate in the first place — would be to run the numbers starting at around M_{20} and seeing what we get. I’ll save that for later, unless somebody wants to beat me to it.

5 Comments

Filed under Crypto, Geekhood, Math