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.

Filed under Crypto, Geekhood, Math

5 responses to “Estimating the digits in a Mersenne prime — for dummies”

1. For what it’s worth, my number theoretic argument didn’t actually use much number theory. And in a way it’s worse than yours because I only used the number of digits in the 44th Mersenne prime to predict the 45th.

2. I’ll see your hackery and raise you one. I’m much less of a mathematician than you, but if there’s one thing I’m “good” at, it’s upping the spreadsheetery to “analyze” a problem.

Like you, I first considered some exponential equation for the digit count. And I have to admit, if you graph the log(base 10) of the digits, it does have a pleasingly near-linear look to it. If you add a linear trend line to that graph, there’s a seemingly sinusoidal pattern to the over-under of the actual digit count. (Clearly I don’t know what I’m talking about, really.)

But like you, I didn’t buy the big jump at the end that would have me believe M45 would have 24 million digits. So what do you do when your hack guess doesn’t feel right? Compound it!

Yeah, so I graphed the log(log()) of the digit count series, and then, basically guessing that the resultant series (conveniently ignoring the first 2 primes, since you can’t do log(log(3)) or log(log(7))) seemed to have an exponential growth to it (hey, R-squared was .9891 — not too bad), I arrived at a wholly fictitious digit count for M45 of 12,392,516. So that’s my guess.

3. I posted the graphs that Todd is talking about above. I have to agree with the 11 million estimate given the trends I see.

How Big?