Skip to content
Cairn Commons
X Sign in
Level A · Machine-checkable Hard Number theory P-oeis-945

Euclid-Mullin sequence

"Does the sequence ... contain every prime? ... [It] was considered by Guy and Nowakowski and later by Shanks, [Wagstaff93] computed the sequence through the 43rd term. The computational problem inherent in continuing the sequence further is the enormous size of the numbers that must be factored.

From the catalogue. Imported from The Formal Conjectures Authors (Google DeepMind and contributors) (Apache-2.0) — original. Nobody has started on it here yet: tasks are created as soon as someone asks for one or submits a claim. A Lean proof is checked against the statement below by the Lean kernel; a curator confirms before the problem counts as resolved.

Start working on it Submit a claim Follow
Cite 
@misc{cairn-oeis-945,
  title        = {Euclid-Mullin sequence},
  author       = {{Cairn Commons contributors}},
  howpublished = {\url{https://cairn-commons.com/problems/oeis-945}},
  year         = {2026},
  note         = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-09-29}
}

Also: CITATION.cff · Atom feed of results

Claims
0
Verified
0
Disputed
0
Refuted
0
On the literature board
0

Current state

No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.

The problem

The question

"Does the sequence ... contain every prime? ... [It] was considered by Guy and Nowakowski and later by Shanks, [Wagstaff93] computed the sequence through the 43rd term. The computational problem inherent in continuing the sequence further is the enormous size of the numbers that must be factored. Already the number has 180 digits."

  • [CrandallPomerance01]

See also [Mullin63].

The Euclid-Mullin sequence starts with . Each subsequent term is the smallest prime factor of one plus the product of all preceding terms. We extend the sequence by and write for the product of the first official terms.

Formal statement (Lean 4)

From Formal Conjectures, module FormalConjectures.OEIS.«945». answer(sorry) marks a yes/no question: a proof of the statement on the right of ↔, or of its negation, answers it.

theorem every_prime_occurs :
    answer(sorry) ↔ ∀ p, p.Prime → ∃ n ≥ 1, a n = p

What counts as progress

  • A Lean proof of the pinned statement (or of its negation, for a yes/no question) — checked by the Lean kernel against the upstream statement; a curator confirms before the problem is marked resolved.
  • Partial results: special cases, weaker bounds, reductions — as verified claims.
  • Computations and numerical evidence with published code (reproducible).
  • Literature: the problem may have been solved or partly solved already. Report it as a literature claim.
  • A precise flaw in the formal statement (a misformalisation) — report it upstream too.

References

  • A000945
  • [Mullin63] A. A. Mullin, "Research Problem 8 (ii)", Bull. Amer. Math. Soc. 69 (1963), p. 737.
  • [Wagstaff93] S. S. Wagstaff, Jr., "Computing Euclid's primes", Bull. Institute Combin. Applications 8 (1993), pp. 23-32.
  • [CrandallPomerance01] R. Crandall and C. Pomerance, Prime Numbers: A Computational Perspective, Springer (2001), p. 6.
  • A. R. Booker, "A variant of the Euclid-Mullin sequence containing every prime," arXiv:1605.08929, Journal of Integer Sequences 19 (2016), Article 16.6.4.

Source and licence

Imported from Formal Conjectures (OEIS), commit e6d1743831c2. Statements and descriptions © The Formal Conjectures Authors, Apache License 2.0; reformatted for this page.