/- 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

Erdős Problem 1209

References:

@[expose] public sectionopen Nat Setnamespace Erdos1209

For every k ≥ 1 and bound m, there is a prime p > m such that k + p is composite: take a prime q > k and, by Dirichlet, a prime p > max m q with p ≡ -k (mod q).

k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero qhunit:IsUnit (-↑k)p:ℕhp:p > max m qhpp:Nat.Prime phpq:↑p = -↑khdvd:q ∣ k + p⊢ ¬Nat.Prime (k + p) exact Nat.not_prime_of_dvd_of_lt hdvd hq.two_le (k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero qhunit:IsUnit (-↑k)p:ℕhp:p > max m qhpp:Nat.Prime phpq:↑p = -↑khdvd:q ∣ k + p⊢ q < k + p All goals completed! 🐙)

The counterexample sequence: a 0 is a prime at least f 0, and a (k + 1) is a prime larger than a k and f (k + 1) with (k + 1) + a (k + 1) composite.

noncomputable def seq (f : ℕ → ℕ) : ℕ → ℕ | 0 => Classical.choose (Nat.exists_infinite_primes (f 0)) | k + 1 => Classical.choose (exists_prime_gt_not_prime_add (k + 1) (max (seq f k) (f (k + 1))) (f:ℕ → ℕk:ℕ⊢ 1 ≤ k + 1 All goals completed! 🐙))

The defining properties of seq f 0.

@[category API, AMS 11] theorem seq_zero_spec (f : ℕ → ℕ) : f 0 ≤ seq f 0 ∧ (seq f 0).Prime := Classical.choose_spec (Nat.exists_infinite_primes (f 0))

The defining properties of seq f (k + 1).

@[category API, AMS 11] theorem seq_succ_spec (f : ℕ → ℕ) (k : ℕ) : max (seq f k) (f (k + 1)) < seq f (k + 1) ∧ (seq f (k + 1)).Prime ∧ ¬ ((k + 1) + seq f (k + 1)).Prime := Classical.choose_spec (exists_prime_gt_not_prime_add (k + 1) (max (seq f k) (f (k + 1))) (f:ℕ → ℕk:ℕ⊢ 1 ≤ k + 1 All goals completed! 🐙))

Let $A={a_1<a_2<\cdots}$ be a sequence of integers which tends to infinity sufficiently fast. If there is an $n$ such that all $n+a_k$ are primes then must there exist infinitely many such $n$?

Erdős [Er80] wrote 'unless I overlook a trivial way of getting a counterexample these questions are quite hopeless'. There is indeed a trivial counterexample (a variant of the construction in [erdosproblems.com/429]): define $a_1=2$ and for $k\geq 2$ let $a_k>a_{k-1}$ be a prime such that $a_k+k\equiv 0\pmod{q_k}$, where $q_k$ is some prime not dividing $k$. This sequence can be made to grow arbitrarily fast

See also [erdosproblems.com/429] and [erdosproblems.com/1102].

f:ℕ → ℕhf:∀ (a : ℕ → ℕ), StrictMono a → (∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f khprime:∀ (k : ℕ), Nat.Prime (seq f k)hinf:{n | ∀ (k : ℕ), Nat.Prime (n + seq f k)}.Infiniten:ℕhn:n ∈ {n | ∀ (k : ℕ), Nat.Prime (n + seq f k)}⊢ n = 0 f:ℕ → ℕhf:∀ (a : ℕ → ℕ), StrictMono a → (∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f khprime:∀ (k : ℕ), Nat.Prime (seq f k)hinf:{n | ∀ (k : ℕ), Nat.Prime (n + seq f k)}.Infiniten:ℕhn:n ∈ {n | ∀ (k : ℕ), Nat.Prime (n + seq f k)}hn0:¬n = 0⊢ False exact (seq_succ_spec f (n - 1)).2.2 (f:ℕ → ℕhf:∀ (a : ℕ → ℕ), StrictMono a → (∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f khprime:∀ (k : ℕ), Nat.Prime (seq f k)hinf:{n | ∀ (k : ℕ), Nat.Prime (n + seq f k)}.Infiniten:ℕhn:n ∈ {n | ∀ (k : ℕ), Nat.Prime (n + seq f k)}hn0:¬n = 0⊢ Nat.Prime (n - 1 + 1 + seq f (n - 1 + 1)) f:ℕ → ℕhf:∀ (a : ℕ → ℕ), StrictMono a → (∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f khprime:∀ (k : ℕ), Nat.Prime (seq f k)hinf:{n | ∀ (k : ℕ), Nat.Prime (n + seq f k)}.Infiniten:ℕhn:n ∈ {n | ∀ (k : ℕ), Nat.Prime (n + seq f k)}hn0:¬n = 0this:Nat.Prime (n + seq f n)⊢ Nat.Prime (n - 1 + 1 + seq f (n - 1 + 1)) rwa [show n - 1 + 1 = n f:ℕ → ℕhf:∀ (a : ℕ → ℕ), StrictMono a → (∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f khprime:∀ (k : ℕ), Nat.Prime (seq f k)hinf:{n | ∀ (k : ℕ), Nat.Prime (n + seq f k)}.Infiniten:ℕhn:n ∈ {n | ∀ (k : ℕ), Nat.Prime (n + seq f k)}hn0:¬n = 0⊢ Nat.Prime (n - 1 + 1 + seq f (n - 1 + 1)) All goals completed! 🐙f:ℕ → ℕhf:∀ (a : ℕ → ℕ), StrictMono a → (∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Nat.Prime (n + a k)) → {n | ∀ (k : ℕ), Nat.Prime (n + a k)}.Infinitehmono:StrictMono (seq f)hbound:∀ (k : ℕ), f k ≤ seq f khprime:∀ (k : ℕ), Nat.Prime (seq f k)hinf:{n | ∀ (k : ℕ), Nat.Prime (n + seq f k)}.Infiniten:ℕhn:n ∈ {n | ∀ (k : ℕ), Nat.Prime (n + seq f k)}hn0:¬n = 0this:Nat.Prime (n + seq f n)⊢ Nat.Prime (n + seq f n) )

For every k ≥ 1 and bound m, there is a prime p > m such that k + p is not squarefree: take a prime q > k and, by Dirichlet, a prime p > m with p ≡ -k (mod q ^ 2).

k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)p:ℕhp:p > mhpp:Nat.Prime phpq:↑p = -↑khdvd:q ^ 2 ∣ k + p⊢ ¬∀ (x : ℕ), Nat.Prime x → ¬x * x ∣ k + p k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)p:ℕhp:p > mhpp:Nat.Prime phpq:↑p = -↑khdvd:q ^ 2 ∣ k + p⊢ ∃ x, Nat.Prime x ∧ x * x ∣ k + p exact ⟨q, hq, k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)p:ℕhp:p > mhpp:Nat.Prime phpq:↑p = -↑khdvd:q ^ 2 ∣ k + p⊢ q * q ∣ k + p rwa [k:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)p:ℕhp:p > mhpp:Nat.Prime phpq:↑p = -↑khdvd:q ^ 2 ∣ k + p⊢ q ^ 2 ∣ k + pk:ℕm:ℕhk:1 ≤ kq:ℕhqk:k + 1 ≤ qhq:Nat.Prime qthis:NeZero (q ^ 2)hunit:IsUnit (-↑k)p:ℕhp:p > mhpp:Nat.Prime phpq:↑p = -↑khdvd:q ^ 2 ∣ k + p⊢ q ^ 2 ∣ k + p⟩

The counterexample sequence for the squarefree variant.

noncomputable def seq' (f : ℕ → ℕ) : ℕ → ℕ | 0 => Classical.choose (Nat.exists_infinite_primes (f 0)) | k + 1 => Classical.choose (exists_prime_gt_not_squarefree_add (k + 1) (max (seq' f k) (f (k + 1))) (f:ℕ → ℕk:ℕ⊢ 1 ≤ k + 1 All goals completed! 🐙))

The defining properties of seq' f (k + 1).

@[category API, AMS 11] theorem seq'_succ_spec (f : ℕ → ℕ) (k : ℕ) : max (seq' f k) (f (k + 1)) < seq' f (k + 1) ∧ (seq' f (k + 1)).Prime ∧ ¬ Squarefree ((k + 1) + seq' f (k + 1)) := Classical.choose_spec (exists_prime_gt_not_squarefree_add (k + 1) (max (seq' f k) (f (k + 1))) (f:ℕ → ℕk:ℕ⊢ 1 ≤ k + 1 All goals completed! 🐙))

What if we ask for $n+a_k$ to be squarefree instead of prime?

A similar construction provides a counterexample to the squarefree question.

f:ℕ → ℕhf:∀ (a : ℕ → ℕ), StrictMono a → (∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f khprime:∀ (k : ℕ), Nat.Prime (seq' f k)hinf:{n | ∀ (k : ℕ), Squarefree (n + seq' f k)}.Infiniten:ℕhn:n ∈ {n | ∀ (k : ℕ), Squarefree (n + seq' f k)}⊢ n = 0 f:ℕ → ℕhf:∀ (a : ℕ → ℕ), StrictMono a → (∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f khprime:∀ (k : ℕ), Nat.Prime (seq' f k)hinf:{n | ∀ (k : ℕ), Squarefree (n + seq' f k)}.Infiniten:ℕhn:n ∈ {n | ∀ (k : ℕ), Squarefree (n + seq' f k)}hn0:¬n = 0⊢ False exact (seq'_succ_spec f (n - 1)).2.2 (f:ℕ → ℕhf:∀ (a : ℕ → ℕ), StrictMono a → (∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f khprime:∀ (k : ℕ), Nat.Prime (seq' f k)hinf:{n | ∀ (k : ℕ), Squarefree (n + seq' f k)}.Infiniten:ℕhn:n ∈ {n | ∀ (k : ℕ), Squarefree (n + seq' f k)}hn0:¬n = 0⊢ Squarefree (n - 1 + 1 + seq' f (n - 1 + 1)) f:ℕ → ℕhf:∀ (a : ℕ → ℕ), StrictMono a → (∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f khprime:∀ (k : ℕ), Nat.Prime (seq' f k)hinf:{n | ∀ (k : ℕ), Squarefree (n + seq' f k)}.Infiniten:ℕhn:n ∈ {n | ∀ (k : ℕ), Squarefree (n + seq' f k)}hn0:¬n = 0this:Squarefree (n + seq' f n)⊢ Squarefree (n - 1 + 1 + seq' f (n - 1 + 1)) rwa [show n - 1 + 1 = n f:ℕ → ℕhf:∀ (a : ℕ → ℕ), StrictMono a → (∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f khprime:∀ (k : ℕ), Nat.Prime (seq' f k)hinf:{n | ∀ (k : ℕ), Squarefree (n + seq' f k)}.Infiniten:ℕhn:n ∈ {n | ∀ (k : ℕ), Squarefree (n + seq' f k)}hn0:¬n = 0⊢ Squarefree (n - 1 + 1 + seq' f (n - 1 + 1)) All goals completed! 🐙f:ℕ → ℕhf:∀ (a : ℕ → ℕ), StrictMono a → (∀ (k : ℕ), f k ≤ a k) → (∃ n, ∀ (k : ℕ), Squarefree (n + a k)) → {n | ∀ (k : ℕ), Squarefree (n + a k)}.Infiniteh0:f 0 ≤ Classical.choose ⋯ ∧ Nat.Prime (Classical.choose ⋯)hmono:StrictMono (seq' f)hbound:∀ (k : ℕ), f k ≤ seq' f khprime:∀ (k : ℕ), Nat.Prime (seq' f k)hinf:{n | ∀ (k : ℕ), Squarefree (n + seq' f k)}.Infiniten:ℕhn:n ∈ {n | ∀ (k : ℕ), Squarefree (n + seq' f k)}hn0:¬n = 0this:Squarefree (n + seq' f n)⊢ Squarefree (n + seq' f n))

Are there $n$ such that $n+2^{2^k}$ is always a prime?

ebarschkis and GPT have proved that there are no $n$ such that $n+2^{2^k}$ is always prime: let $n\geq 3$ be any odd integer. If $k$ is chosen sufficiently large, and $p=n+2^{2^{k}}$ is prime, then the multiplicative order of $2^{2^k}\pmod{p}$, say $m$ is odd, and hence if $l$ is chosen such that $2^l\equiv 1\pmod{m}$ then $p\mid n+2^{2^{k+rl}}$ for all $r\geq 1$.

This was formalized in Lean by Barschkis using ChatGPT.

@[category research solved, question, AMS 11, formal_proof using lean4 at "https://github.com/ebarschkis/ErdosProblem/blob/main/Problem1209/Formalization.lean"] theorem erdos_1209.parts.iii.a : ¬ ∃ n : ℕ, ∀ k : ℕ, (n + 2 ^ (2 ^ k)).Prime := ⊢ ¬∃ n, ∀ (k : ℕ), Nat.Prime (n + 2 ^ 2 ^ k) All goals completed! 🐙

Are there $n$ such that $n+2^{2^k}$ is always squarefree?

@[category research open, question, AMS 11] theorem erdos_1209.parts.iii.b : ∃ n : ℕ, ∀ k : ℕ, Squarefree (n + 2 ^ (2 ^ k)) := ⊢ ∃ n, ∀ (k : ℕ), Squarefree (n + 2 ^ 2 ^ k) All goals completed! 🐙

Are there $n$ such that $n+2^{2^k}$ is infinitely often a prime?

@[category research open, question, AMS 11] theorem erdos_1209.parts.iii.c : ∃ n : ℕ, {k | (n + 2 ^ (2 ^ k)).Prime}.Infinite := ⊢ ∃ n, {k | Nat.Prime (n + 2 ^ 2 ^ k)}.Infinite All goals completed! 🐙

Are there $n$ such that $n+2^{2^k}$ is infinitely often squarefree?

@[category research open, question, AMS 11] theorem erdos_1209.parts.iii.d : ∃ n : ℕ, {k | Squarefree (n + 2 ^ (2 ^ k))}.Infinite := ⊢ ∃ n, {k | Squarefree (n + 2 ^ 2 ^ k)}.Infinite All goals completed! 🐙end Erdos1209