Problem Statement

Lucas-Lehmer Test: for

p

{\displaystyle p}

an odd prime, the Mersenne number

2

p

− 1

{\displaystyle 2^{p}-1}

is prime if and only if

2

p

− 1

{\displaystyle 2^{p}-1}

divides

S ( p − 1 )

{\displaystyle S(p-1)}

where

S ( n + 1 )

( S ( n )

)

2

− 2

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

, and

S ( 1 )

4

{\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:

#lang racket
(require math)

(define (mersenne-prime? p)
  (divides? (- (expt 2 p) 1) (S (- p 1))))

(define (S n)
  (if (= n 1) 4 (- (sqr (S (- n 1))) 2)))

(define (loop p)
  (when (mersenne-prime? p)
    (displayln p))
  (loop (next-prime p)))

(loop 3)