# Lucas-Lehmer test for Mersenne numbers (J)

### From LiteratePrograms

# theory

According to the wikipedia article, first we define a sequence as follows:

Then a Mersenne number (*M*_{p} = 2^{p}− 1) is prime iff

# practice

The sequence recurrence is straightfoward to define:
*NB. we define as a dyad so that we may do the modulo arithmetic on every iteration.*

seq =: dyad : 'x|_2+*:y'

and, sure enough, the first few terms of the sequence agree with OEIS A00301.
*NB. 4x is 4 represented as an e xtended (arbitrary-precision) integer.*

0 seq^:(i.8) 4x 4 14 194 37634 1416317954 2005956546822746114 4023861667741036022825635656102100994 16191462721115671781777559070120513664958590125499158514329308740975788034

Now we define a function, using the iteration operator (**^:**) to find the **res**idue *s*_{p − 2}(mod *M*_{p}):

res =: monad : '(_1+2x^y) seq^:(y-2) 4x'

# wrapping up

We can double check our implementation against the examples in the article:

res each 3 11 +-+----+ |0|1736| +-+----+ (0=res) each 3 11 +-+-+ |1|0| +-+-+

Or we can test primality in a different manner by counting (**#**) factors (**q:**) of the first few Mersenne numbers (*M*_{p} = 2^{p}− 1), then checking that two sets of indications (zero residue or single factor) agree:

mpf =: monad : '#q:_1+2x^y' >((0=res)=(1=mpf)) each p:1+i.15 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Alternatively, we could wrap everything up into the following single-line definition:

llmp =: monad : '0=(_1+2x^y) ([|_2+[:*:])^:(y-2) 4x'

Download code |