/- Copyright 2025 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 409

Reference: erdosproblems.com/409

@[expose] public sectionopen scoped Topology ArithmeticFunction.sigma Natopen Filternamespace Erdos409def erdos_409.parts.i.answer (n : ℕ) : ℕ := sorry

How many iterations of $n\mapsto\phi(n) + 1$ are needed before a prime is reached?

-- Formalisation note: the sequence of iterates always terminates if `n > 0` -- since it is strictly decreasing unless the input is prime, at which point -- it becomes static. See also https://oeis.org/A39651 @[category research open, question value, AMS 11] theorem erdos_409.parts.i (n : ℕ) (hn : 0 < n) : IsLeast { i | (φ · + 1)^[i] n |>.Prime } (erdos_409.parts.i.answer n) := n:ℕhn:0 < n⊢ IsLeast {i | Nat.Prime ((fun x ↦ φ x + 1)^[i] n)} (i.answer n) All goals completed! 🐙

If $n > 0$, then the iteration $n\mapsto\phi(n) + 1$ necessarily reaches a prime.

n:ℕih:∀ m < n, 0 < m → ∃ i, Nat.Prime ((fun x ↦ φ x + 1)^[i] m)hn:0 < nhp:¬Nat.Prime nh1:1 < nhlt:φ n < nhne:φ n ≠ n - 1hdec:φ n + 1 < nhpos:0 < φ n + 1i:ℕhi:Nat.Prime ((fun x ↦ φ x + 1)^[i] (φ n + 1))⊢ Nat.Prime ((fun x ↦ φ x + 1)^[i] (φ n + 1)) All goals completed! 🐙-- Formalisation note: it's possible that solution to `erdos_409.parts.i` needs to be -- expressed asymptotically. To handle this we include `IsTheta`, `IsBigO` -- and `IsLittleO` variants below. Since a solution is not known this necessitates -- the use of an `answer` definition left as `sorry`. Trivial or sub-optimal solutions -- will therefore exist to the asymptotic formalisations. A true solution to -- the asymptotic variants should have a degree of optimality or non-triviality to it. def erdos_409.parts.i.isTheta.answer : ℕ → ℝ := sorry

Let $c(n)$ be the minimum number of iterations of $n\mapsto\phi(n) + 1$ before a prime is reached. What is $\Theta(c(n))$?

@[category research open, question value, AMS 11] theorem erdos_409.parts.i.isTheta (c : ℕ → ℕ) (h : ∀ n > 0, IsLeast { i | (φ · + 1)^[i] n |>.Prime } (c n)) : (fun n => (c n : ℝ)) =Θ[atTop] erdos_409.parts.i.isTheta.answer := c:ℕ → ℕh:∀ n > 0, IsLeast {i | Nat.Prime ((fun x ↦ φ x + 1)^[i] n)} (c n)⊢ (fun n ↦ ↑(c n)) =Θ[atTop] isTheta.answer All goals completed! 🐙def erdos_409.parts.i.isBigO.answer : ℕ → ℝ := sorry

Let $c(n)$ be the minimum number of iterations of $n\mapsto\phi(n) + 1$ before a prime is reached. Find the simplest function $g(n)$ such that $c(n) = O(g(n))$?

@[category research open, question value, AMS 11] theorem erdos_409.parts.i.isBigO (c : ℕ → ℕ) (h : ∀ n > 0, IsLeast { i | (φ · + 1)^[i] n |>.Prime } (c n)) : (fun n => (c n : ℝ)) =O[atTop] erdos_409.parts.i.isBigO.answer := c:ℕ → ℕh:∀ n > 0, IsLeast {i | Nat.Prime ((fun x ↦ φ x + 1)^[i] n)} (c n)⊢ (fun n ↦ ↑(c n)) =O[atTop] isBigO.answer All goals completed! 🐙def erdos_409.parts.i.isLittleO.answer : ℕ → ℝ := sorry

Let $c(n)$ be the minimum number of iterations of $n\mapsto\phi(n) + 1$ before a prime is reached. Find the simplest function $g(n)$ such that $c(n) = o(g(n))$?

@[category research open, question value, AMS 11] theorem erdos_409.parts.i.isLittleO (c : ℕ → ℕ) (h : ∀ n > 0, IsLeast { i | (φ · + 1)^[i] n |>.Prime } (c n)) : (fun n => (c n : ℝ)) =o[atTop] erdos_409.parts.i.isLittleO.answer := c:ℕ → ℕh:∀ n > 0, IsLeast {i | Nat.Prime ((fun x ↦ φ x + 1)^[i] n)} (c n)⊢ (fun n ↦ ↑(c n)) =o[atTop] isLittleO.answer All goals completed! 🐙

Can infinitely many $n$ reach the same prime under the iteration $n\mapsto\phi(n) + 1$?

@[category research open, question, AMS 11] theorem erdos_409.parts.ii : ∃ (p : ℕ) (hp : p.Prime), { n | ∃ i, (φ · + 1)^[i] n = p }.Infinite := ⊢ ∃ p, ∃ (_ : Nat.Prime p), {n | ∃ i, (fun x ↦ φ x + 1)^[i] n = p}.Infinite All goals completed! 🐙def erdos_409.parts.iii.answer : ℝ := sorry

What is the density of $n$ which reach any fixed prime under the iteration $n\mapsto\phi(n) + 1$?

@[category research open, question value, AMS 11] theorem erdos_409.parts.iii (p : ℕ) (h : p.Prime) : { n | ∃ i, (φ · + 1)^[i] n = p }.HasDensity erdos_409.parts.iii.answer := p:ℕh:Nat.Prime p⊢ {n | ∃ i, (fun x ↦ φ x + 1)^[i] n = p}.HasDensity iii.answer All goals completed! 🐙def erdos_409.variants.sigma.answer (n : ℕ) : ℕ := sorry

If the iteration $n\mapsto\sigma(n) - 1$ starting at $n > 1$ reaches a prime, how many iterations are needed before a prime is reached?

-- Formalisation note: termination of this sequence is not known in general since -- it is strictly increasing except at primes, so it is assumed as a hypothesis. @[category research open, question value, AMS 11] theorem erdos_409.variants.sigma (n : ℕ) (hn : n > 1) (hterm : ∃ i, (σ 1 · - 1)^[i] n |>.Prime) : IsLeast { i | (σ 1 · - 1)^[i] n |>.Prime } (erdos_409.variants.sigma.answer n) := n:ℕhn:n > 1hterm:∃ i, Nat.Prime ((fun x ↦ (σ 1) x - 1)^[i] n)⊢ IsLeast {i | Nat.Prime ((fun x ↦ (σ 1) x - 1)^[i] n)} (sigma.answer n) All goals completed! 🐙

If $n > 1$ then the iteration $n\mapsto\sigma(n) - 1$ necessarily reaches a prime. Note: this is open — it is not clear that the σ iteration always terminates, since it is non-decreasing (unlike the φ iteration which is strictly decreasing).

@[category research open, AMS 11] theorem erdos_409.variants.sigma_termination (n : ℕ) (hn : n > 1) : ∃ i, (σ 1 · - 1)^[i] n |>.Prime := n:ℕhn:n > 1⊢ ∃ i, Nat.Prime ((fun x ↦ (σ 1) x - 1)^[i] n) All goals completed! 🐙-- Formalisation note: See the above formalisation note for the rationale -- for including asymptotic variants def erdos_409.variants.sigma_isTheta.answer : ℕ → ℝ := sorry

Let $c(n)$ be the minimum number of iterations of $n\mapsto\sigma(n) - 1$ before a prime is reached. What is $\Theta(c(n))$?

@[category research open, question value, AMS 11] theorem erdos_409.variants.sigma_isTheta (c : ℕ → ℕ) (h : ∀ n > 1, IsLeast { i | (σ 1 · - 1)^[i] n |>.Prime } (c n)) : (fun n => (c n : ℝ)) =Θ[atTop] erdos_409.variants.sigma_isTheta.answer := c:ℕ → ℕh:∀ n > 1, IsLeast {i | Nat.Prime ((fun x ↦ (σ 1) x - 1)^[i] n)} (c n)⊢ (fun n ↦ ↑(c n)) =Θ[atTop] sigma_isTheta.answer All goals completed! 🐙def erdos_409.variants.sigma_isBigO.answer : ℕ → ℝ := sorry

Let $c(n)$ be the minimum number of iterations of $n\mapsto\sigma(n) - 1$ before a prime is reached. Find the simplest function $g(n)$ such that $c(n) = O(g(n))$?

@[category research open, question value, AMS 11] theorem erdos_409.variants.sigma_isBigO (c : ℕ → ℕ) (h : ∀ n > 1, IsLeast { i | (σ 1 · - 1)^[i] n |>.Prime } (c n)) : (fun n => (c n : ℝ)) =O[atTop] erdos_409.variants.sigma_isBigO.answer := c:ℕ → ℕh:∀ n > 1, IsLeast {i | Nat.Prime ((fun x ↦ (σ 1) x - 1)^[i] n)} (c n)⊢ (fun n ↦ ↑(c n)) =O[atTop] sigma_isBigO.answer All goals completed! 🐙def erdos_409.variants.sigma_isLittleO.answer : ℕ → ℝ := sorry

Let $c(n)$ be the minimum number of iterations of $n\mapsto\sigma(n) - 1$ before a prime is reached. Find the simplest function $g(n)$ such that $c(n) = o(g(n))$?

@[category research open, question value, AMS 11] theorem erdos_409.variants.sigma_isLittleO (c : ℕ → ℕ) (h : ∀ n > 1, IsLeast { i | (σ 1 · - 1)^[i] n |>.Prime } (c n)) : (fun n => (c n : ℝ)) =o[atTop] erdos_409.variants.sigma_isLittleO.answer := c:ℕ → ℕh:∀ n > 1, IsLeast {i | Nat.Prime ((fun x ↦ (σ 1) x - 1)^[i] n)} (c n)⊢ (fun n ↦ ↑(c n)) =o[atTop] sigma_isLittleO.answer All goals completed! 🐙

Is it true that iterates of $n\mapsto\sigma(n) - 1$ always reach a prime?

@[category research open, question, AMS 11] theorem erdos_409.variants.sigma_prime_termination : ∀ n > 1, ∃ i, (σ 1 · - 1)^[i] n |>.Prime := ⊢ ∀ n > 1, ∃ i, Nat.Prime ((fun x ↦ (σ 1) x - 1)^[i] n) All goals completed! 🐙end Erdos409