/- Copyright 2026 The Formal Conjectures Authors. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at https://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. -/ module public import FormalConjecturesUtil

Euclid–Fortunate prime coverage

OEIS A067836 starts with $2$. Each later term is the gap from the product of all previous terms to the least prime strictly greater than that product plus one.

References:

@[expose] public sectionnamespace OeisA67836

The finite set in which the least prime strictly above n is sought.

def primeCandidates (n : ℕ) : Finset ℕ := (Finset.Icc (n + 1) (2 * (n + 1))).filter Nat.Prime

Bertrand's postulate makes the finite prime-candidate set nonempty.

n:ℕp:ℕhp:Nat.Prime phnp:n + 1 < php_le:p ≤ 2 * (n + 1)⊢ (primeCandidates n).Nonempty n:ℕp:ℕhp:Nat.Prime phnp:n + 1 < php_le:p ≤ 2 * (n + 1)⊢ p ∈ primeCandidates n n:ℕp:ℕhp:Nat.Prime phnp:n + 1 < php_le:p ≤ 2 * (n + 1)⊢ (n + 1 ≤ p ∧ p ≤ 2 * (n + 1)) ∧ Nat.Prime p exact ⟨⟨n:ℕp:ℕhp:Nat.Prime phnp:n + 1 < php_le:p ≤ 2 * (n + 1)⊢ n + 1 ≤ p All goals completed! 🐙, hp_le⟩, hp⟩

The least prime strictly greater than n, found in the Bertrand interval.

def leastPrimeAbove (n : ℕ) : ℕ := (primeCandidates n).min' (primeCandidates_nonempty n)

The chosen number is strictly above the bound and is prime.

n:ℕhmem:(n + 1 ≤ (Finset.filter Nat.Prime (Finset.Icc (n + 1) (2 * (n + 1)))).min' ⋯ ∧ (Finset.filter Nat.Prime (Finset.Icc (n + 1) (2 * (n + 1)))).min' ⋯ ≤ 2 * (n + 1)) ∧ Nat.Prime ((Finset.filter Nat.Prime (Finset.Icc (n + 1) (2 * (n + 1)))).min' ⋯)hbound:n < leastPrimeAbove nhprime:Nat.Prime (leastPrimeAbove n)⊢ n < leastPrimeAbove n ∧ Nat.Prime (leastPrimeAbove n) All goals completed! 🐙

The least prime above n is no larger than any other prime above n.

n:ℕp:ℕhnp:n < php:Nat.Prime php_bound:¬p ≤ 2 * (n + 1)hmem:(n + 1 ≤ (Finset.filter Nat.Prime (Finset.Icc (n + 1) (2 * (n + 1)))).min' ⋯ ∧ (Finset.filter Nat.Prime (Finset.Icc (n + 1) (2 * (n + 1)))).min' ⋯ ≤ 2 * (n + 1)) ∧ Nat.Prime ((Finset.filter Nat.Prime (Finset.Icc (n + 1) (2 * (n + 1)))).min' ⋯)hbound:leastPrimeAbove n ≤ 2 * (n + 1)⊢ leastPrimeAbove n ≤ p All goals completed! 🐙

No number strictly between n and leastPrimeAbove n is prime.

@[category API, AMS 11] lemma not_prime_of_lt_leastPrimeAbove (n p : ℕ) (hnp : n < p) (hp : p < leastPrimeAbove n) : ¬ p.Prime := n:ℕp:ℕhnp:n < php:p < leastPrimeAbove n⊢ ¬Nat.Prime p n:ℕp:ℕhnp:n < php:p < leastPrimeAbove nhp_prime:Nat.Prime p⊢ False n:ℕp:ℕhnp:n < php:p < leastPrimeAbove nhp_prime:Nat.Prime pthis:leastPrimeAbove n ≤ p⊢ False All goals completed! 🐙

A convenient criterion for computing the least prime above a concrete bound.

n:ℕp:ℕhnp:n < php:Nat.Prime phmin:∀ (q : ℕ), n < q → q < p → ¬Nat.Prime qh:¬p ≤ leastPrimeAbove nhlt:leastPrimeAbove n < p⊢ False All goals completed! 🐙

The recursive state records the latest term and the product of all official terms so far.

structure State where term : ℕ product : ℕ

The state after n official terms, with the empty state initialized by term and product one.

def state : ℕ → State | 0 => ⟨1, 1⟩ | n + 1 => let previous := state n let next := leastPrimeAbove (previous.product + 1) - previous.product ⟨next, previous.product * next⟩

OEIS A067836, with the convenience value a 0 = 1 preceding its official first term.

def a (n : ℕ) : ℕ := (state n).term@[category test, AMS 11] theorem a_0 : a 0 = 1 := ⊢ a 0 = 1 All goals completed! 🐙@[category test, AMS 11] theorem a_1 : a 1 = 2 := ⊢ a 1 = 2 All goals completed! 🐙@[category test, AMS 11] theorem a_2 : a 2 = 3 := ⊢ a 2 = 3 All goals completed! 🐙@[category test, AMS 11] theorem a_3 : a 3 = 5 := ⊢ a 3 = 5 All goals completed! 🐙@[category test, AMS 11] theorem a_4 : a 4 = 7 := ⊢ a 4 = 7 All goals completed! 🐙set_option maxRecDepth 10000 in @[category test, AMS 11] theorem a_5 : a 5 = 13 := ⊢ a 5 = 13 All goals completed! 🐙

OEIS A067836 asks: "Do all primes occur in the sequence?"

@[category research open, question, AMS 11] theorem conjecture : ∀ p, p.Prime → ∃ n ≥ 1, a n = p := ⊢ ∀ (p : ℕ), Nat.Prime p → ∃ n ≥ 1, OeisA67836.a n = p All goals completed! 🐙end OeisA67836