** Numworks and DM42: Lucas-Lehmer Primality Tes**t

**Introduction**

The Lucas-Lehmer Primality tests whether integers of the form 2^p - 1 are prime by repeating the loop p-2 times:

s_i+1 = s_i^2 - 2

with the initial value s_0 = 4.

At the end of the loop, if s = 0 mod (2^p - 1), then integer 2^p - 1 is a prime number.

Caution: this test fails when p = 2. The user will be asked to input an integer greater than 2.

**Numworks Python Script: llt.py**

from math import *

# Lucas-Lehmer Test

# 2020-12-06 EWS

p=float(input("p (>2)? "))

s=4

m=2**p-1

for i in range(p-2):

# repeat p-2 times

s=(s*s-2)%m

print("Mersenne Number:")

print(m)

if s==0:

print("Prime")

else:

print("Not Prime")

**HP 42S/DM42 Program LLT**

00 {66-Byte Prgm}

01 LBL "LLT"

02 "P (>2)?"

03 PROMPT

04 STO 01

05 ENTER

06 2

07 X<>Y

08 Y↑X

09 1

10 -

11 STO 04

12 R↓

13 2

14 -

15 STO 02

16 4

17 STO 03

18 LBL 00

19 RCL 03

20 X↑2

21 2

22 -

23 RCL 04

24 MOD

25 STO 03

26 DSE 02

27 GTO 00

28 RCL 04

29 "M= "

30 ARCL ST X

31 AVIEW

32 STOP

33 RCL 03

34 X=0?

35 "PRIME"

36 X=0?

37 AVIEW

38 END

Registers

R01: p

R02: p - 2

R03: s

R04: m = 2^p - 1

**Examples**

p = 3

m = 7

Prime

p = 4

m = 15

Not Prime

p = 5

m = 31

Not Prime

p = 15

m = 32767

Not Prime

p = 20

m = 1048575

Not Prime

Source:

Cook, John D. "Searching for Mersenne Primes" John D. Cook Consulting November 28, 2018. Retrieved December 5, 2020. https://www.johndcook.com/blog/2018/11/28/searching-for-mersenne-primes/

"Lucas-Lehmer primality test" Wikipedia. Last edited June 29, 2020. Retrieved December 5, 2020.

https://en.wikipedia.org/wiki/Lucas–Lehmer_primality_test

Eddie

Thank you for content. I like it and my site is different for your site. please visit my site. แจกเครดิตฟรี ฝากถอนง่าย

ReplyDeleteHi Eddie,

ReplyDeleteThank you for all the work. A few little errors: the python code should use int(...) instead of float(...), and p = 5, m = 31 is actually Prime :-)

Regards, Marko