6
\$\begingroup\$

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

Improve this question
\$\endgroup\$
7
  • \$\begingroup\$ Related \$\endgroup\$
    – Peter Taylor
    Jul 7, 2017 at 11:49
  • \$\begingroup\$ @PeterTaylor, No, I request the LLT. The other one just any possible test. \$\endgroup\$
    – MEE
    Jul 7, 2017 at 11:51
  • 5
    \$\begingroup\$ 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? \$\endgroup\$
    – Peter Taylor
    Jul 7, 2017 at 11:56
  • 4
    \$\begingroup\$ He didn't say it was a duplicate, he said Related \$\endgroup\$
    – Mayube
    Jul 7, 2017 at 12:44
  • 4
    \$\begingroup\$ Also I'm pretty sure this falls under unobservable criteria \$\endgroup\$
    – Mayube
    Jul 7, 2017 at 12:45

7 Answers 7

Reset to default
4
\$\begingroup\$

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

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Isn't this a snippet? \$\endgroup\$
    – Olivier Grégoire
    Jul 7, 2017 at 12:48
  • \$\begingroup\$ @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. \$\endgroup\$
    – ovs
    Jul 7, 2017 at 12:52
  • \$\begingroup\$ Ok, it's a full program. I didn't read it as such, my bad! :) \$\endgroup\$
    – Olivier Grégoire
    Jul 7, 2017 at 12:57
3
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

Haskell, 47 43 41 bytes

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!

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ 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! \$\endgroup\$
    – Sergii Martynenko Jr
    Jul 7, 2017 at 19:49
2
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ The Lucas Lehmer test only applies to Mersenne primes. And 2 is no Mersenne prime. So they have to apply to odd primes only. \$\endgroup\$
    – MEE
    Jul 7, 2017 at 12:42
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – C McAvoy
    Jul 7, 2017 at 12:44
  • \$\begingroup\$ ok. misunderstood you: L<2>=4, 4 % 3 != 0 \$\endgroup\$
    – MEE
    Jul 7, 2017 at 12:47
2
\$\begingroup\$

PHP, 58 bytes

for($s=4;++$i+1<$argn;)$s=($s**2-2)%(2**$argn-1);echo+!$s;

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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?
Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.