E008: Lucas–Lehmer scan (prime exponents)

Preview figure for E008
Preview figure for E008

Tags: number-theory, quantitative-exploration, visualization See: Valid Tags.

Highlights

  • Run the Lucas–Lehmer test for many prime exponents \(p\).

  • Record timing and residue behavior for composite vs. prime outcomes.

  • Produce a reproducible “scan report” (which \(p\) were tested, which passed).

Goal

Empirically explore Mersenne primality testing by scanning prime exponents \(p\) and applying the Lucas–Lehmer test to \(M_p = 2^p - 1\).

Background (quick refresher)

Research question

For prime exponents \(p \le P\), how does:

  • runtime of the Lucas–Lehmer test scale with \(p\)?

  • the distribution of final residues (mod \(M_p\)) differ between prime and composite outcomes?

Why this qualifies as a mathematical experiment

  • Finite procedure: enumerate prime exponents up to a bound and test them.

  • Observable(s): pass/fail, final residue, and runtime.

  • Parameter space: vary \(P\) and optional “max tests” cap.

  • Outcome: a dataset (tested \(p\) values) and plots/tables that suggest scaling behavior.

  • Failure modes: naive implementations can be slow; parameters bound the search to keep runs feasible.

Experiment design

Computation

  • Enumerate prime exponents \(p\) up to a bound \(P\).

  • For each \(p\), compute \(M_p = 2^p - 1\) and run Lucas–Lehmer:

    • \(s_0 = 4\)

    • \(s_{k+1} = s_k^2 - 2 \pmod{M_p}\)

    • \(M_p\) is prime iff \(s_{p-2} \equiv 0 \pmod{M_p}\).

  • Record (at minimum): \(p\), pass/fail, final residue, and wall time.

Outputs

  • table: scanned exponents with result and time

  • plot: \(p\) vs. runtime (often log-scale is helpful)

  • plot: residue magnitude / patterns (optional)

How to run

make run EXP=e008

or:

uv run python -m mathxlab.experiments.e008

Notes / pitfalls

  • Only run Lucas–Lehmer for prime \(p\); if \(p\) is composite then \(M_p\) is composite.

  • The test is defined for odd prime \(p\); treat \(p=2\) separately (\(M_2=3\) is prime).

  • Keep bounds modest at first; the cost grows quickly with \(p\).

Extensions

  • Add a “pre-sieve” that checks for small factors before running Lucas–Lehmer.

  • Compare your timings to published implementations (as a sanity check, not a competition).

Published run snapshot

If this experiment is included in the docs gallery, include the published snapshot (report + params).

Reproduce:

make run EXP=e008

Parameters

  • p_max: 10000

  • max_tests: 600

Results

  • tested exponents: 600

  • Mersenne primes found: 19

Prime exponents p where M_p is prime

2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253

Notes

  • LLT is a deterministic primality test specialized to M_p = 2^p - 1.

  • Only prime exponents p need to be tested: if 2^n-1 is prime, then n must be prime.

params.json (snapshot)
{
  "max_tests": 600,
  "p_max": 10000
}

References

See References.

[Caldwell, 2021, contributors, 2025, Mersenne Research, 2024]