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

This Ruby code calculates Mersenne primes, which are prime numbers of the form $M_p = 2^p - 1$, where $p$ is also a prime number. It first defines two helper functions:

is_prime(p) checks if a given number p is a prime number.
is_mersenne_prime(p) checks if a given number p is a Mersenne prime.

The main program then finds Mersenne primes in the range [2, upb_prime], where upb_prime is set to a value determined by the precision of the calculations. It iterates through the range, checking if each number p is both a prime number and a Mersenne prime. If it is, it prints M followed by the value of p. The program stops when it has found upb_count Mersenne primes.

Here is a brief description of how the program works:

The is_prime function uses a simple trial division algorithm to check if a given number is prime.
The is_mersenne_prime function uses a more complex algorithm to check if a given number is a Mersenne prime.
The main program iterates through the range [2, upb_prime], calling the is_prime and is_mersenne_prime functions on each number.
If a number is both a prime number and a Mersenne prime, it prints M followed by the value of p.
The program stops when it has found upb_count Mersenne primes.

Source code in the ruby programming language

def is_prime ( p )
  return true  if p == 2
  return false if p <= 1 || p.even?
  (3 .. Math.sqrt(p)).step(2) do |i|
    return false  if p % i == 0
  end
  true
end

def is_mersenne_prime ( p )
  return true  if p == 2
  m_p = ( 1 << p ) - 1
  s = 4
  (p-2).times { s = (s ** 2 - 2) % m_p }
  s == 0
end

precision = 20000   # maximum requested number of decimal places of 2 ** MP-1 #
long_bits_width = precision / Math.log(2) * Math.log(10)
upb_prime = (long_bits_width - 1).to_i / 2    # no unsigned #
upb_count = 45      # find 45 mprimes if int was given enough bits #

puts " Finding Mersenne primes in M[2..%d]:" % upb_prime

count = 0
for p in 2..upb_prime
  if is_prime(p) && is_mersenne_prime(p)
    print "M%d " % p
    count += 1
  end
  break  if count >= upb_count
end
puts