Numworks and DM42: Lucas-Lehmer Primality Test

 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