E012: Fermat pseudoprimes and Carmichael numbers (counterexamples)

Preview figure for E012
Preview figure for E012

Tags: number-theory, counterexample-search, visualization See: Valid Tags.

Highlights

  • Counterexamples to naive Fermat primality testing: base-a pseudoprimes and Carmichael numbers.

  • Writes reproducible artifacts (params.json, report.md, and figures).

  • Designed to surface patterns and “looks-true-until-it-breaks” behavior.

Goal

Counterexamples to naive Fermat primality testing: base-a pseudoprimes and Carmichael numbers.

Background (quick refresher)

Research question

Which prime-related claim, heuristic, or algorithm breaks first under a clean, controlled computational sweep, and what does the smallest or clearest counterexample (or deviation) look like?

Why this qualifies as a mathematical experiment

  • Finite procedure: run a bounded search / sweep with recorded parameters.

  • Observable(s): counts, gaps, residues, runtime scaling, or first counterexample witnesses.

  • Parameter space: vary bounds (and sometimes algorithmic choices).

  • Outcome: plots/tables + “witness objects” for failures.

  • Reproducibility: outputs saved to out/e012/ with a parameter snapshot.

Experiment design

  • Computation: bounded enumeration / sampling with explicit limits.

  • Outputs: figures and a short report.md summarizing what was found.

  • Artifacts written:

  • figures/fig_01_cumulative_counts.png

  • figures/fig_02_smallest_factor_hist.png

  • params.json

  • report.md

How to run

make run EXP=e012

or:

uv run python -m mathxlab.experiments.e012

Notes / pitfalls

  • “No counterexample found” only means “none found within the configured bounds”.

  • For probabilistic tests (when used), treat outcomes as evidence, not proof.

Extensions

  • Increase bounds and rerun (recording runtime and memory).

  • Compare alternative heuristics or algorithms on the same parameter grid.

  • Turn found deviations into new, tighter conjectures.

Published run snapshot

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

Reproduce:

make run EXP=e012 ARGS="--seed 1"

Parameters

  • seed: 1

  • n_max: 200000

  • base a: 2

  • max_listed: 25

Summary

  • Fermat pseudoprimes to base 2: 106

  • Carmichael numbers: 22

First examples (Fermat pseudoprimes)

#

n

1

341

2

561

3

645

4

1105

5

1387

6

1729

7

1905

8

2047

9

2465

10

2701

11

2821

12

3277

13

4033

14

4369

15

4371

16

4681

17

5461

18

6601

19

7957

20

8321

21

8481

22

8911

23

10261

24

10585

25

11305

First examples (Carmichael numbers)

#

n

1

561

2

1105

3

1729

4

2465

5

2821

6

6601

7

8911

8

10585

9

15841

10

29341

11

41041

12

46657

13

52633

14

62745

15

63973

16

75361

17

101101

18

115921

19

126217

20

162401

21

172081

22

188461

Notes

  • Fermat’s test is one-way: primes pass, but some composites also pass.

  • Carmichael numbers are the strongest counterexamples: they pass for all coprime bases.

  • Detection here uses Korselt’s criterion (squarefree + divisibility conditions).

params.json (snapshot)
{
  "base": 2,
  "max_listed": 25,
  "n_max": 200000,
  "seed": 1
}

References

See References.