5
\$\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

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

\$\endgroup\$
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

\$\endgroup\$
  • \$\begingroup\$ Isn't this a snippet? \$\endgroup\$ – Olivier Grégoire Jul 7 '17 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 '17 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 '17 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.

\$\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!

\$\endgroup\$
  • 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 '17 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.

\$\endgroup\$
  • 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 - Reinstate Monica Jul 7 '17 at 12:42
  • \$\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 '17 at 12:44
  • \$\begingroup\$ ok. misunderstood you: L<2>=4, 4 % 3 != 0 \$\endgroup\$ – MEE - Reinstate Monica Jul 7 '17 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!

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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