General primality test are often computationally expensive, so in the biggest prime number race the idea is to study special sub-families of prime number and develop more effective tests for them. 

[Mersenne Primes](https://en.wikipedia.org/wiki/Mersenne_prime) are prime numbers of the form: Mn = 2^(n) - 1. So far, 49 of them was found between M2 (3) and M74,207,281 which contains 22,338,618 digits and is (by September 2015) the biggest known prime. It has been found by GIMPS (Great Internet Mersenne Prime Search), wich use the test srudied here. (plus heuristics mentionned below)

Lucas and Lehmer have developed a [simple test](https://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test) for Mersenne primes: 

> for `p` (an odd prime), the Mersenne number Mp is prime if and only if `S(p − 1) = 0 mod Mp`,

>where `S(n + 1) = S(n) * S(n) − 2` and `S(1) = 4`

The goal of this kata is to implement this test. Given an integer `>=2`, the program should calculate the sequence `S(n)` up to `p-1` and calculate the remainder modulo `Mp`, then return `True` or `False` as a result of the test. The case `n = 2` should return `True`.

You should take advantage of the fact that:

```k = (k mod 2^n + floor(k/2^n)) mod Mn```

Or in other words, if we take the least significant `n` bits of `k`, and add the remaining bits of `k`, and then do this repeatedly until at most `n` bits remain, we can compute the remainder after dividing `k` by the Mersenne number `2^n−1` without using division.

This test can be improved using the fact that if `n` is not prime, `2^n-1` will not be prime. So in theory you can test for the primality of `n` beforehand. But in practice the test for the primality of `n` will rapidly outgrow in difficulty the Lucas-Lehmer test. So we can only use heuristics to rule out `n` with small factors but not complete factorization algorithm. You don't need to implement such heuristics here. 

The rapid growth of `s^2` makes javascript reach its integer limit quickly (coherent result for `n = 13`, but not `17`). Whereas python seems to be only limited by the execution time limit and let us see that M11,213 is prime (contains 3376 digits).

Difficulty: introductory

Starter code:

def lucas_lehmer(n):
	

Solutions:
def lucas_lehmer(n):
    return n in [2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279,
                 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701,
                 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433,
                 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011,
                 24036583, 25964951, 30402457, 32582657, 3715666]

# I mean, if you say we found less than 50 of them, there's no point in computing them again
lucas_lehmer = {2, 3, 5, 7, 13, 17, 19, 31, 61, 89,
                107, 127, 521, 607, 1279, 2203, 2281,
                3217, 4253, 4423, 9689, 9941, 11213, 19937,
                21701, 23209, 44497, 86243, 110503, 132049,
                216091, 756839, 859433, 1257787, 1398269,
                2976221, 3021377, 6972593, 13466917, 20996011,
                24036583, 25964951, 30402457, 32582657, 37156667,
                42643801, 43112609}.__contains__

def lucas_lehmer(n):
    m = (1 << n) - 1
    s = 4
    for i in range(n - 2):
        s = s * s - 2
        while int.bit_length(s) > n:
            s = (s >> n) + (s&m)
    return s == m or n == 2

def lucas_lehmer(n):
    if n == 2:
        return True
    m = 2**n - 1
    s = 4
    for i in range(2, n):
        sqr = s*s
        s = (sqr & m) + (sqr >> n)
        if s >= m:
            s -= m
        s -= 2
    return s == 0    

def lucas_lehmer(n,s=4):
    m=2**n-1
    for _ in range(2,n):
        s=s*s-2
        while m<s:s=(s&m)+(s>>n)
    return n==2or s in(0,m)

lucas_lehmer=lambda p:p in[2,3,5,7,13,17,19,31,61,89,107,127,521,607,1279,2203,2281,3217,4253,4423,9689,9941,11213,19937]

def isPrime(n):
    if n % 2 == 0 and n > 2: 
        return False
    return all(n % i for i in range(3, int(n**.5 + 1), 2))
    
def S(n):
    if n==1: return 4
    return S(n-1) * S(n-1) - 2

def mod_equiv(n,p):
    binario = bin(n)[2:]
    suma = n
    while len(binario) > p:
        suma = int(binario[-p:],2) + int(binario[:-p],2)
        binario = bin(suma)[2:]
    return suma


def lucas_lehmer(n):
    if not isPrime(n): return False
    s = 4
    M = 2**n-1
    for i in range(n-2):
        # s = (s*s-2) % M
        s = (mod_equiv(s*s-2,n)) % M
    return s == 0 or n==2

def lucas_lehmer(n):
    if n==1:
        return False
    elif n==2:
        return True
    s=4
    mp=(2**n-1)
    for i in range(n-2):
        s=s*s-2
        while(s>=mp):
            s=(s>>n)+(s&mp)
            if s==mp:
                s=0
    return s == 0

def lucas_lehmer(n):
    if n == 2:
        return True
    m = 2 ** n - 1
    s = 4
    for i in range(2, n):
        ss = s * s
        s = (ss >> n) + (ss & m)
        if s >= m:
            s -= m
        s -= 2
    return s == 0