/-
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 FormalConjecturesUtilErdős Problem 430
References:
[ErGr80] Erdős, P. and Graham, R., Old and new problems and results in combinatorial number theory. Monographies de L'Enseignement Mathematique (1980).
The question is equivalent to the first part of Erdős Problem 385 (an observation of Sarosh Adenwalla recorded on both problem pages).
@[expose] public sectionnamespace Erdos430open FilterThe terms of the sequence of Erdős Problem 430 for a given $n$: the integers $m$ with $1 < m < n$ all of whose prime factors are $> n - m$.
The decreasing sequence $a_1 > a_2 > \cdots$ of the problem lists the elements of this set in decreasing order: $a_1 = n - 1$ is its largest element and $a_k$ is its largest element below $a_{k-1}$. The integer $1$ has no prime factors and is not a term of the sequence, which stops instead, as in the example on erdosproblems.com: for $n = 8$ the sequence is $7, 5$.
def terms (n : ℕ) : Finset ℕ := (Finset.Ioo 1 n).filter fun m => ∀ p ∈ m.primeFactors, n - m < pFor example if $n=8$ we have $a_1=7$ and $a_2=5$ and then must stop.
@[category test, AMS 11]
theorem terms_eight : terms 8 = {5, 7} := ⊢ terms 8 = {5, 7}
All goals completed! 🐙
The first term of the sequence is $a_1 = n - 1$, the largest element of terms n.
@[category API, AMS 11]
theorem isGreatest_sub_one {n : ℕ} (hn : 3 ≤ n) : IsGreatest (terms n : Set ℕ) (n - 1) := n:ℕhn:3 ≤ n⊢ IsGreatest (↑(terms n)) (n - 1)
n:ℕhn:3 ≤ n⊢ n - 1 ∈ ↑(terms n)n:ℕhn:3 ≤ nm:ℕhm:m ∈ ↑(terms n)⊢ m ≤ n - 1
n:ℕhn:3 ≤ n⊢ n - 1 ∈ ↑(terms n) n:ℕhn:3 ≤ n⊢ (1 < n - 1 ∧ n - 1 < n) ∧ ∀ p ∈ (n - 1).primeFactors, n - (n - 1) < p
refine ⟨⟨n:ℕhn:3 ≤ n⊢ 1 < n - 1 All goals completed! 🐙, n:ℕhn:3 ≤ n⊢ n - 1 < n All goals completed! 🐙⟩, fun p hp => ?_⟩
n:ℕhn:3 ≤ np:ℕhp:p ∈ (n - 1).primeFactorsthis:1 < p⊢ n - (n - 1) < p
All goals completed! 🐙
n:ℕhn:3 ≤ nm:ℕhm:m ∈ ↑(terms n)⊢ m ≤ n - 1 n:ℕhn:3 ≤ nm:ℕhm:(1 < m ∧ m < n) ∧ ∀ p ∈ m.primeFactors, n - m < p⊢ m ≤ n - 1
All goals completed! 🐙Fix some integer $n$ and define a decreasing sequence in $[1,n)$ by $a_1=n-1$ and, for $k\geq 2$, letting $a_k$ be the greatest integer in $[1,a_{k-1})$ such that all of the prime factors of $a_k$ are $>n-a_k$.
Is it true that, for sufficiently large $n$, not all of this sequence can be prime?
@[category research open, question, AMS 11]
theorem erdos_430 : ∀ᶠ n in atTop, ¬ ∀ m ∈ terms n, m.Prime := ⊢ ∀ᶠ (n : ℕ) in atTop, ¬∀ m ∈ terms n, Nat.Prime m
All goals completed! 🐙end Erdos430