/-
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 FormalConjecturesUtilEuclid–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.PrimeBertrand'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
refine ⟨p, ?_⟩ n:ℕp:ℕhp:Nat.Prime phnp:n + 1 < php_le:p ≤ 2 * (n + 1)⊢ p ∈ primeCandidates n
simp only [primeCandidates, Finset.mem_filter, Finset.mem_Icc] 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 ⟨⟨by n:ℕp:ℕhp:Nat.Prime phnp:n + 1 < php_le:p ≤ 2 * (n + 1)⊢ n + 1 ≤ p omega 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.
@[category API, AMS 11]
lemma leastPrimeAbove_spec (n : ℕ) :
n < leastPrimeAbove n ∧ (leastPrimeAbove n).Prime := by n:ℕ⊢ n < leastPrimeAbove n ∧ Nat.Prime (leastPrimeAbove n)
have hmem := Finset.min'_mem (primeCandidates n) (primeCandidates_nonempty n) n:ℕhmem:(primeCandidates n).min' ⋯ ∈ primeCandidates n⊢ n < leastPrimeAbove n ∧ Nat.Prime (leastPrimeAbove n)
simp only [primeCandidates, Finset.mem_filter, Finset.mem_Icc] at hmem 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' ⋯)⊢ n < leastPrimeAbove n ∧ Nat.Prime (leastPrimeAbove n)
have hbound : n < leastPrimeAbove n := by
simpa only [leastPrimeAbove, primeCandidates, Nat.lt_iff_add_one_le] using hmem.1.1 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 n⊢ n < leastPrimeAbove n ∧ Nat.Prime (leastPrimeAbove n) 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 n⊢ n < leastPrimeAbove n ∧ Nat.Prime (leastPrimeAbove n)
have hprime : (leastPrimeAbove n).Prime := by
simpa only [leastPrimeAbove, primeCandidates] using hmem.2 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) 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)
exact ⟨hbound, hprime⟩ All goals completed! 🐙
The least prime above n is no larger than any other prime above n.
@[category API, AMS 11]
lemma leastPrimeAbove_le (n p : ℕ) (hnp : n < p) (hp : p.Prime) :
leastPrimeAbove n ≤ p := by n:ℕp:ℕhnp:n < php:Nat.Prime p⊢ leastPrimeAbove n ≤ p
by_cases hp_bound : p ≤ 2 * (n + 1) pos n:ℕp:ℕhnp:n < php:Nat.Prime php_bound:p ≤ 2 * (n + 1)⊢ leastPrimeAbove n ≤ pneg n:ℕp:ℕhnp:n < php:Nat.Prime php_bound:¬p ≤ 2 * (n + 1)⊢ leastPrimeAbove n ≤ p
· pos n:ℕp:ℕhnp:n < php:Nat.Prime php_bound:p ≤ 2 * (n + 1)⊢ leastPrimeAbove n ≤ p have hp_mem : p ∈ primeCandidates n := by
simp only [primeCandidates, Finset.mem_filter, Finset.mem_Icc] n:ℕp:ℕhnp:n < php:Nat.Prime php_bound:p ≤ 2 * (n + 1)⊢ (n + 1 ≤ p ∧ p ≤ 2 * (n + 1)) ∧ Nat.Prime p pos n:ℕp:ℕhnp:n < php:Nat.Prime php_bound:p ≤ 2 * (n + 1)hp_mem:p ∈ primeCandidates n⊢ leastPrimeAbove n ≤ p
exact ⟨⟨by n:ℕp:ℕhnp:n < php:Nat.Prime php_bound:p ≤ 2 * (n + 1)⊢ n + 1 ≤ p pos n:ℕp:ℕhnp:n < php:Nat.Prime php_bound:p ≤ 2 * (n + 1)hp_mem:p ∈ primeCandidates n⊢ leastPrimeAbove n ≤ p omega All goals completed! 🐙pos n:ℕp:ℕhnp:n < php:Nat.Prime php_bound:p ≤ 2 * (n + 1)hp_mem:p ∈ primeCandidates n⊢ leastPrimeAbove n ≤ p, hp_bound⟩, hp⟩pos n:ℕp:ℕhnp:n < php:Nat.Prime php_bound:p ≤ 2 * (n + 1)hp_mem:p ∈ primeCandidates n⊢ leastPrimeAbove n ≤ p
exact Finset.min'_le _ _ hp_mem All goals completed! 🐙
· neg n:ℕp:ℕhnp:n < php:Nat.Prime php_bound:¬p ≤ 2 * (n + 1)⊢ leastPrimeAbove n ≤ p have hmem := Finset.min'_mem (primeCandidates n) (primeCandidates_nonempty n) neg n:ℕp:ℕhnp:n < php:Nat.Prime php_bound:¬p ≤ 2 * (n + 1)hmem:(primeCandidates n).min' ⋯ ∈ primeCandidates n⊢ leastPrimeAbove n ≤ p
simp only [primeCandidates, Finset.mem_filter, Finset.mem_Icc] at hmem neg 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' ⋯)⊢ leastPrimeAbove n ≤ p
have hbound : leastPrimeAbove n ≤ 2 * (n + 1) := by
simpa only [leastPrimeAbove, primeCandidates] using hmem.1.2 neg 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 ≤ pneg 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
omega 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 := by n:ℕp:ℕhnp:n < php:p < leastPrimeAbove n⊢ ¬Nat.Prime p
intro hp_prime n:ℕp:ℕhnp:n < php:p < leastPrimeAbove nhp_prime:Nat.Prime p⊢ False
have := leastPrimeAbove_le n p hnp hp_prime n:ℕp:ℕhnp:n < php:p < leastPrimeAbove nhp_prime:Nat.Prime pthis:leastPrimeAbove n ≤ p⊢ False
omega All goals completed! 🐙A convenient criterion for computing the least prime above a concrete bound.
@[category API, AMS 11]
lemma leastPrimeAbove_eq (n p : ℕ) (hnp : n < p) (hp : p.Prime)
(hmin : ∀ q, n < q → q < p → ¬ q.Prime) : leastPrimeAbove n = p := by n:ℕp:ℕhnp:n < php:Nat.Prime phmin:∀ (q : ℕ), n < q → q < p → ¬Nat.Prime q⊢ leastPrimeAbove n = p
apply Nat.le_antisymm (leastPrimeAbove_le n p hnp hp) n:ℕp:ℕhnp:n < php:Nat.Prime phmin:∀ (q : ℕ), n < q → q < p → ¬Nat.Prime q⊢ p ≤ leastPrimeAbove n
by_contra h n:ℕp:ℕhnp:n < php:Nat.Prime phmin:∀ (q : ℕ), n < q → q < p → ¬Nat.Prime qh:¬p ≤ leastPrimeAbove n⊢ False
have hlt : leastPrimeAbove n < p := by n:ℕp:ℕhnp:n < php:Nat.Prime phmin:∀ (q : ℕ), n < q → q < p → ¬Nat.Prime q⊢ leastPrimeAbove n = p n:ℕp:ℕhnp:n < php:Nat.Prime phmin:∀ (q : ℕ), n < q → q < p → ¬Nat.Prime qh:¬p ≤ leastPrimeAbove nhlt:leastPrimeAbove n < p⊢ False omega n:ℕp:ℕhnp:n < php:Nat.Prime phmin:∀ (q : ℕ), n < q → q < p → ¬Nat.Prime qh:¬p ≤ leastPrimeAbove nhlt:leastPrimeAbove n < p⊢ False n:ℕp:ℕhnp:n < php:Nat.Prime phmin:∀ (q : ℕ), n < q → q < p → ¬Nat.Prime qh:¬p ≤ leastPrimeAbove nhlt:leastPrimeAbove n < p⊢ False
exact hmin (leastPrimeAbove n) (leastPrimeAbove_spec n).1 hlt (leastPrimeAbove_spec n).2 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 := by ⊢ a 0 = 1 rfl All goals completed! 🐙@[category test, AMS 11]
theorem a_1 : a 1 = 2 := by ⊢ a 1 = 2
decide All goals completed! 🐙@[category test, AMS 11]
theorem a_2 : a 2 = 3 := by ⊢ a 2 = 3
decide All goals completed! 🐙@[category test, AMS 11]
theorem a_3 : a 3 = 5 := by ⊢ a 3 = 5
decide All goals completed! 🐙@[category test, AMS 11]
theorem a_4 : a 4 = 7 := by ⊢ a 4 = 7
decide All goals completed! 🐙set_option maxRecDepth 10000 in
@[category test, AMS 11]
theorem a_5 : a 5 = 13 := by ⊢ a 5 = 13
decide 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 := by ⊢ ∀ (p : ℕ), Nat.Prime p → ∃ n ≥ 1, OeisA67836.a n = p
sorry All goals completed! 🐙end OeisA67836