Lucas-Lehmer Test

Author

Eric W. Weisstein
June 8, 2004

This notebook downloaded from http://mathworld.wolfram.com/notebooks/PrimeNumbers/Lucas-LehmerTest.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/Lucas-LehmerTest.html.

©2005 Wolfram Research, Inc. except for portions noted otherwise

Code

LucasLehmer[p_]:=NestList[Mod[#^2-2,2^p-1]&,4,p-2]
LucasLehmerResidue[p_]:=Nest[Mod[#^2-2,2^p-1]&,4,p-2]

Enumeration

{#,LucasLehmer[#]}&/@Take[MersennePrimeIndices,6]//ColumnForm

LucasLehmerResidue/@Range[2,10]

LucasLehmerResidue/@Prime[Range[10]]

Print[{#,LucasLehmerResidue[#]//Timing,PrimeQ[Mersenne[#]]//Timing}]&/@MersennePrimeIndices

Print[{#,LucasLehmerResidue[#]//Timing}]&/@Drop[MersennePrimeIndices,28]

MersennePrimeIndices