1

I wrote the code below, to get the Lucas-Lehmer series up to p, for p the exponent of a Mersenne number. After checking it I found that it doesn't work for some primes p such as 11, 23, 29 etc. Any help will be very valuable!

Here's the code:

def ll_series (p):
    ll_list=[4]
    print 4
    for i in range(1, p+1):
        ll_list.append((ll_list[i-1]**2 - 2) % (2**p-1))
        print(ll_list[i])
    return ll_list
Arca Ege Cengiz
  • 315
  • 3
  • 16
nik panik
  • 11
  • 1
  • 2
  • 1
    What does "it doesn't work" mean? Can you show an example input, the output your function gives, and the output you would expect? – glibdud Jul 06 '18 at 12:24
  • Also, you've tagged this python 3, but you used the python 2 `print` syntax. Which is it? (I've replaced the python 3 tag for now with the generic python tag, which is more appropriate anyway. If you prefer, you can add the appropriate version tag back.) Also also, your function isn't indented properly. Please double-check code you post to be sure that others will be able to reproduce the issue without making too many assumptions. – glibdud Jul 06 '18 at 12:32
  • Thank you for your comments! – nik panik Jul 06 '18 at 15:23

2 Answers2

1

The Lucas-Lehmer test tests if a Mersenne number is prime. 11 is not a Mersenne number therefore the test fails. Mersennse number is - M_n = 2^n-1.

http://mathworld.wolfram.com/MersenneNumber.html

p.s the implementation can be more efficient if you calculate M=(2^p-1) only once

Tom Ron
  • 5,906
  • 3
  • 22
  • 38
1

Try this:

lucas_lehmer = [4]

def mersenne(n):
    return (2 ** n) - 1

def ll(n):
    global lucas_lehmer
    if len(lucas_lehmer) < n:
        for num in range(n-1):
            lucas_lehmer.append(lucas_lehmer[-1] ** 2 - 2)
    return lucas_lehmer[n-1]

def check_prime(n):
    m = mersenne(n)
    if ll(n - 1) % m == 0:
        return m
    else:
        return -1

Things to note:

  • You need to call the check_prime function
  • The input to the check_prime function must be a smaller prime number
  • Not all prime numbers produce prime results in the Mersenne sequence.
  • If 2^n - 1 is not prime, it will return -1

I have also cleared the code up a bit and made it easier to read.

Arca Ege Cengiz
  • 315
  • 3
  • 16