Sunday, December 13, 2020

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


3 comments:

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

    ReplyDelete
  2. ยินดีต้อนรับสู่ UPLAY365.COM เว็บพนันออนไลน์ All In One ที่รวมเว็บพนันออนไลน์อันดับ 1 ไว้ที่เดียวกันมากที่สุด ไม่ว่าจะเป็น เกมส์ไพ่ ที่เป็นที่นิยม เช่นบาคาร่า แบล็คแจ็ค เสือมังกร หรือจะเป็น รูเล็ต สล็อตออนไลน์ คีโน โป๊กเกอร์ forex ไก่ชน เกมส์ยิงปลา แทงบอล แทงบาส เทนนิส ESPORT แทงมวยไทย และอื่นๆอีกมากมาย พร้อมเทคโนโลยีชั้นนำจากผู้ผลิตซอฟต์แวร์เกมส์ระดับโลก ความน่าเชื่อถือได้มาเป็นอันดับ 1 สามารถเล่นได้ทั้งบนคอมพิวเตอร์ , มือถือ ระบบ android และ IOS *คาสิโนออนไลน์ : สามารถเลือกเล่นกับคาสิโนชั้นนำดังนี้ SexyBaccarat, AG Casino, GOLD Casino, SA Casino, W88 Casino, D88 Casino, WM Casino, GD Casino เป็นต้น *แทงบอล : U กีฬา (U SPORTS) , S กีฬา (S SPORTS) มั่นใจได้เลยว่า อัตราการจ่ายค่าน้ำดีที่สุดต้อง uplay365 เหมาะสำหรับทั้งนักพนันมืออาชีพและ มือใหม่ โดยทางเรามีพนักงานคอยสอนเรื่องการแทงบอลเบื้องต้น แทงง่าย อัตราจ่ายดี *สล็อตออนไลน์ ,เกมส์ยิงปลา : JOKER123,PLAYTECH และอื่นๆ อีกมากมาย ทั้งหมดนี้ สามารถเล่นได้ใน 1 ยูสเซอร์เท่านั้น สนใจสมัครสมาชิกรับเครดิตฟรี สามารถสมัครได้ตนเองที่หน้าเว็บ หรือติดต่อ Callcenter โดย ทางเรามีพนักงานไว้บริการและแก้ปัญหา ตลอด 24 ชั่วโมง สอบถามข้อมูลเพิ่มเติมได้กับแอดมินได้ตลอด 24 ชม.ค่ะ

    SA
    HONGBO

    ReplyDelete
  3. Hi Eddie,

    Thank 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

    ReplyDelete

TI-Nspire: Templates to Plot Functions, Parametric Equations, and Sequences

 TI-Nspire:  Templates to Plot Functions, Parametric Equations, and Sequences Introduction The following are sample templates to plot functi...