How to resolve the algorithm Lucas-Lehmer test step by step in the F# 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 F# programming language

Source code in the fsharp programming language

let rec s mp n =
  if n = 1 then 4I % mp else ((s mp (n - 1)) ** 2 - 2I) % mp

[ for p in 2..47 do
    if p = 2 || s ((1I <<< p) - 1I) (p - 1) = 0I then
      yield p ]


let IsMersennePrime exponent =
    if exponent <= 1 then failwith "Exponent must be >= 2"
    let prime = 2I ** exponent - 1I;

    let rec LucasLehmer i acc =
        match i with
        | x when x = exponent - 2 -> acc
        | x -> LucasLehmer (x + 1) ((acc*acc - 2I) % prime)
 
    LucasLehmer 0 4I = 0I


let IsMersennePrime exponent =
    if exponent <= 1 then failwith "Exponent must be >= 2"
    let prime = 2I ** exponent - 1I;

    let LucasLehmer =
        [| 1 .. exponent-2 |] |> Array.fold (fun acc _ -> (acc*acc - 2I) % prime) 4I
 
    LucasLehmer = 0I