How to resolve the algorithm Lucas-Lehmer test step by step in the Haskell programming language

Problem Statement
Step by Step Solution
Sourcecode

Problem Statement

Lucas-Lehmer Test: for

{\displaystyle p}

an odd prime, the Mersenne number

− 1

{\displaystyle 2^{p}-1}

is prime if and only if

− 1

{\displaystyle 2^{p}-1}

divides

S ( p − 1 )

{\displaystyle S(p-1)}

where

S ( n + 1 )

( S ( n )

)

− 2

{\displaystyle S(n+1)=(S(n))^{2}-2}

, and

S ( 1 )

{\displaystyle S(1)=4}

Calculate all Mersenne primes up to the implementation's maximum precision, or the 47th Mersenne prime (whichever comes first).

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Lucas-Lehmer test step by step in the Haskell programming language

This Haskell code generates and prints the first 45 Mersenne primes. Mersenne primes are prime numbers of the form 2^p - 1, where p is also a prime number.

Here's a breakdown of the code:

lucasLehmer function:
- Checks if a given number p is a Mersenne prime using the Lucas-Lehmer test.
- For p = 2, it returns True because 2 is the only even Mersenne prime.
- For other p, it calculates s(2^p-1, p-1) mod (2^p-1) using the function s.
- Returns True if the result of s is 0, indicating that p is a Mersenne prime.
s function:
- Calculates the sequence s(m, n) = (s(m, n-1)^2 - 2) mod m.
- This sequence is used to perform the Lucas-Lehmer test.
sieve function:
- Implements the Sieve of Eratosthenes to generate prime numbers.
- Takes a list of numbers xs and filters out numbers that are divisible by a given prime p.
printMersennes function:
- Takes a list of numbers and prints each number with the prefix "M" to indicate that it's a Mersenne prime.
main function:
- Generates the first 45 Mersenne primes using take 45 $ filter lucasLehmer $ sieve [2..].
- Invokes the printMersennes function to print the primes.

Source code in the haskell programming language

module Main
  where

main = printMersennes $ take 45 $ filter lucasLehmer $ sieve [2..]

s mp 1 = 4 `mod` mp
s mp n = ((s mp $ n-1)^2-2) `mod` mp

lucasLehmer 2 = True
lucasLehmer p = s (2^p-1) (p-1) == 0

printMersennes = mapM_ (\x -> putStrLn $ "M" ++ show x)


sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p > 0]