E009: Small-factor scan for Mersenne numbers

Preview figure for E009
Preview figure for E009

Tags: number-theory, quantitative-exploration, visualization See: Valid 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)

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

make run EXP=e009

or:

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

Reproduce:

make run EXP=e009

Parameters

  • p_max: 10000

  • max_tests: 800

  • q_max: 5000000

  • require_q_prime: True

Results

  • tested exponents: 800

  • with small factor found: 369

Sample (first 20 with a found factor)

p

factor q

3

7

5

31

7

127

11

23

13

8191

17

131071

19

524287

23

47

29

233

37

223

41

13367

43

431

47

2351

53

6361

59

179951

71

228479

73

439

79

2687

83

167

97

11447

Notes

  • The congruence filter q ≡ 1 (mod 2p) is necessary but not sufficient.

  • A found q certifies M_p is composite; it does not factor M_p completely.

params.json (snapshot)
{
  "max_tests": 800,
  "p_max": 10000,
  "q_max": 5000000,
  "require_q_prime": true
}

References

See References.

[Caldwell, 2021, contributors, 2025, Inc., 2025]