# E009: Small-factor scan for Mersenne numbers

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

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

**Tags:** `number-theory`, `quantitative-exploration`, `visualization`
See: {doc}`../tags`.

## Highlights

- Quickly eliminate many $M_p$ candidates by finding small prime factors.
- Use the structure of possible factors of $M_p$ to reduce wasted work.
- Show how often “trivial” factors appear in a range of exponents.

## Goal

Explore how often Mersenne numbers $M_p = 2^p - 1$ (with prime $p$) have **small factors**, and how
a lightweight sieve can filter candidates before running Lucas–Lehmer.

## Background (quick refresher)

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

## Research question

For prime exponents $p \le P$ and a factor bound $q \le Q$:

- how many $M_p$ have a factor below $Q$?
- how much compute can be saved by sieving before Lucas–Lehmer?

## Why this qualifies as a mathematical experiment

- **Finite procedure:** scan a finite range of $p$ and candidate factors.
- **Observable(s):** first small factor found (if any), counts by $p$ and by factor size.
- **Parameter space:** vary $P$ and $Q$.
- **Outcome:** tables/plots that show factor frequency and sieve effectiveness.
- **Failure modes:** incomplete sieve bounds can mislead; clearly report $Q$ as a limitation.

## Experiment design

### Computation

For fixed prime exponent $p$, any prime factor $q$ of $M_p$ satisfies:

- $q \equiv 1 \pmod{2p}$ (a common necessary condition used to generate candidates)

A practical sieve approach:

- Generate candidate primes $q$ of the form $q = 2pk + 1$ up to $Q$.
- For each candidate prime $q$, check:

  - $2^p \equiv 1 \pmod{q}$

  If true, then $q$ divides $M_p$.

### Outputs

- table: per $p$, smallest factor found (or “none up to $Q$”)
- plot: $p$ vs. smallest factor (when present)
- summary: fraction of $p$ eliminated by the sieve

## How to run

```bash
make run EXP=e009
```

or:

```bash
uv run python -m mathxlab.experiments.e009
```

## Notes / pitfalls

- This is a **bounded** sieve: “no factor found” only means “none found up to $Q$”.
- Prime testing for $q$ should be fast; for small $Q$, a simple deterministic method is fine.
- Report both $P$ and $Q$ prominently in the report.

## Extensions

- Combine with E008: run Lucas–Lehmer only on exponents not eliminated by the sieve.
- Track how much wall time is saved by the combined pipeline.

## Published run snapshot

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

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

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

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

:::

## References

See {doc}`../references`.

{cite:p}`WikipediaContributors2025MersennePrime,Caldwell2021MersennePrimesPrimePages,OEIS2025A001348MersenneNumbers`

## Related experiments

- {doc}`e042` (Repunit primes (small k scan))
- {doc}`e007` (Mersenne growth (bits and digits))
- {doc}`e008` (Lucas–Lehmer scan (prime exponents))
- {doc}`e010` (Even perfect numbers from Mersenne primes)
- {doc}`e011` (Heuristic rarity of Mersenne primes)