Numworks and DM42: Lucas-Lehmer Primality Test
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
