sidef-scripts/Math/power_of_2_plus_5_primes_lucas-lehmer.sf

#!/usr/bin/ruby

# Primality test for primes of the form 2^n + 5.

# First few exponents of such primes, are:
#   1, 3, 5, 11, 47, 53, 141, 143, 191, 273, 341, 16541, 34001, 34763, 42167, ...

# The primality test was derived from the Lucas-Lehmer primality test for Mersenne primes.

# See also:
#   https://oeis.org/A059242

func is_pow2_plus5_prime(n) {   # defined for n >= 11

    var M = (1<<n + 5)
    var S = 4

    M % 3 == 0 && return false      # divisible by 3 and 9

    n.times {
       S = (powmod(S, 2, M) - 2)
    }

    S == 194
}

for n in (11..400) {
    if (is_pow2_plus5_prime(n)) {
        say n
    }
}