# E008: Lucas–Lehmer scan (prime exponents)

```{figure} ../_static/experiments/e008_hero.png
:width: 80%
:alt: Preview figure for E008
```

```{figure} ../_static/experiments/e008_hero_2.png
:width: 80%
:alt: Preview figure for E008
```

**Tags:** `number-theory`, `quantitative-exploration`, `visualization`
See: {doc}`../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)

- {doc}`../background/mersenne-primes`

## 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

```bash
make run EXP=e008
```

or:

```bash
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).

```{include} ../reports/e008.md
:start-after: "<!-- REPORT:BEGIN -->"
:end-before: "<!-- REPORT:END -->"
```

::: {dropdown} params.json (snapshot)
:open:

```{literalinclude} ../params/e008.json
:language: json
```

:::

## References

See {doc}`../references`.

{cite:p}`WikipediaContributors2025LucasLehmerPrimalityTest,Caldwell2021MersennePrimesPrimePages,MersenneResearchInc2024GIMPSMathPrimeNet`

## Related experiments

- {doc}`e009` (Small-factor scan for Mersenne numbers)
- {doc}`e042` (Repunit primes (small k scan))
- {doc}`e048` (Carmichael numbers: Korselt scan + Fermat counterexamples)
- {doc}`e049` (Wieferich primes (base 2): scan and quotient visualization)
- {doc}`e002` (Even Perfect Numbers — Generator and Growth)