Programming Praxis – Mersenne Primes

In today’s Programming Praxis exercise, our goal is to calculate the Mersenne prime exponents up to 256. Let’s get started, shall we?

A quick import:

import Data.Numbers.Primes

The Mersenne primes can be determine with a simple list comprehension. Although the Lucas-Lehmer test officially doesn’t work for M2, in practice it works just fine so there is no need to make it a special case.

mersennes :: [Int]
mersennes = [p | p <- primes,
    iterate (\n -> mod (n^2 - 2) (2^p - 1)) 4 !! p-2 == 0]

A test shows that the algorithm is working correctly. Piece of cake.

main :: IO ()
main = print $ takeWhile (<= 256) mersennes
               == [2,3,5,7,13,17,19,31,61,89,107,127]
About these ads

Tags: , , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: