Prime time for Oktoberfest

[essentialsaltes]

USC lost to the Ducks got licked by the Beavers and UCLA discovers the largest known Mersenne prime.

Mersenne primes, you'll recall, are those in the form (2^p) - 1, where p is itself prime.

When p=2, you get 2^2 - 1 = 3, which is prime
When p=3, you get 2^3 - 1 = 7, which is prime
When p=5, you get 2^5 - 1 = 31, which is prime
When p=7, you get 2^7 - 1 = 127, which is prime

Seems like a pattern is forming, but with p=11, you get 2047, which is obviously 23 x 89, i.e. not a prime.

This new prime is only the 46th Mersenne prime known. I would be hard-pressed to show that 43,112,609 is prime, but this new one is 2^43,112,609 - 1, a number with nearly 13 million digits.

---

Oktoberfest in Munich seems to be changing for the better, as if that were possible.

Speaking of which, Chalet Edelweiss now seems to be open for business, although there's still some odd construction material about. The menu doesn't thrill me, but German beer on tap calls to me.

Comments

[rizwank.livejournal.com]

For finding whether a single number is prime or not?

Sieve : O((nlogn)(loglogn))

The divisor method should be much cheaper than that, it'll only do n^(1/2) divisions. [Of course, the proof lies in whether the division/int test is more expensive than the above multiplication, and, of course, it is. But by how much?]

Neat link though. Enjoyed reading it =)

[essentialsaltes.livejournal.com]

Obviously you can partially incorporate the sieve by testing only the odd numbers from 3 to n. That'll save you half your time. And if you make use of known primes, you'll get even more efficient. Looks like you'll only have to test fewer than 1000 primes to get to n. But maybe using a list is cheating.