Golf the Lucas Lehmer Primality Test

your task is to write a program that uses the Lucas-Lehmer primality test to check whether an input number is prime or not. This prime number candidate has the form 2p-1 with p being prime. (Mersenne prime number)

The Lucas-Lehmer-test

The n-th Mersenne number is prime if it is a divisor of the (n-1)-th Lucas-Lehmer number (LLN). You can calculate the LLN, similiar to the Fibonacci numbers, based on a recursive algorithm:

L<n> = (L<n-1>)^2 - 2


The LLN for 2 is 14. So, for p=3, LLN<3-1>=14

Evaluation

• You have to submit a function that takes p as input (Remember: 2^p-1)
• The shortest solution will win.
• Your solution has to use the Lucas-Lehmer test
• The code must be executable.
• Output: boolean value or 1=prime/0=not prime

Tests:

p --> 2^p-1  --> LLN<n-1> --> ?
3 --> 7      --> 14  --> prime
5 --> 31     --> 37634 > prime (1214*31)


Good Luck

• Related Commented Jul 7, 2017 at 11:49
• @PeterTaylor, No, I request the LLT. The other one just any possible test. Commented Jul 7, 2017 at 11:51
• I linked to an answer which implements the LLT. Besides, what does "related" mean if a question which asks for a specific test of a property is not related to a question which asks for any test of the same property? Commented Jul 7, 2017 at 11:56
• He didn't say it was a duplicate, he said Related Commented Jul 7, 2017 at 12:44
• Also I'm pretty sure this falls under unobservable criteria Commented Jul 7, 2017 at 12:45

Python 2, 51 bytes

p=input()
s=4
exec's=(s*s-2)%(2**p-1);'*(p-2)
s>0>x


Try it online!

Output is via exit code

• Isn't this a snippet? Commented Jul 7, 2017 at 12:48
• @OlivierGrégoire it takes input in the first line and outputs by crashing / not crashing in the last line, which is meant by Output is via exit code. This is a valid output method.
– ovs
Commented Jul 7, 2017 at 12:52
• Ok, it's a full program. I didn't read it as such, my bad! :) Commented Jul 7, 2017 at 12:57

Mathematica 44 Bytes

(s@3=14;s@n_:=Mod[s[n-1]^2-2,2^#-1];s@#==0)&


Test:

{#, %[#]} & /@ Prime[Range[2, 20]]


Too bad we can't use MersennePrimeExponentQ (22 bytes) since it doesn't appear to always use the LLT.

Thanks @Kittsil for saving me 2 bytes!

f n=iterate(\v->mod(v^2-2)$2^n-1)4!!n-2<1  Try it online! • Using pattern matching instead of guards saves you 4 bytes in this case p 2=4;p n=p(x-1)^2-2 Try it online! Commented Jul 7, 2017 at 19:49 Python 3, 61 bytes l=lambda x:4*(x<3)or l(x-1)**2-2 f=lambda p:not l(p)%(2**p-1)  Try it online! I'd like to note that the Lucas-Lehmer test only applies to odd primes Mersenne numbers of the form 2p-1 where p is an odd prime. This program uses a recursive function for the Lucas-Lehmer numbers, and then a function that just tests if the n-th LLN is divisible by Mn. • The Lucas Lehmer test only applies to Mersenne primes. And 2 is no Mersenne prime. So they have to apply to odd primes only. Commented Jul 7, 2017 at 12:42 • @PaulStrobach Should have been more specific. The Lucas-Lehmer test only applies to Mersenne primes of the form 2^p-1 where p is an odd prime. I am aware that 2 is no Mersenne prime, but 2^2-1 is, which will not be detected by this test. Commented Jul 7, 2017 at 12:44 • ok. misunderstood you: L<2>=4, 4 % 3 != 0 Commented Jul 7, 2017 at 12:47 PHP, 58 bytes for($s=4;++$i+1<$argn;)$s=($s**2-2)%(2**$argn-1);echo+!$s;


Try it online!

05AB1E, 11 bytes

o<4IÍFnÍ}sÖ


Try it online!

Explanation

o<            # push 2^p-1
4           # push 4
IÍF        # p-2 times do:
nÍ      # square and subtract 2
}     # end loop
sÖ   # LLN(n) % Mp == 0


If we didn't need boolean value output we could save a byte with 4IÍFnÍIo<% which returns 0 for prime and non-zero otherwise.

APL, 28 bytes

{0=(¯1+2*⍵)|(¯2+×⍨)⍣(⍵-2)⊢4}


Explanation:

                         ⊢4    ⍝ to the number 4,
⍣(⍵-2)      ⍝ apply this function ⍵-2 times,
(¯2+×⍨)            ⍝ N*N - 2
(¯1+2*⍵)|                   ⍝ modulo 2^⍵ - 1
0=                            ⍝ is the result 0?