/-
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.
-/modulepublicimportFormalConjecturesUtil
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@[categoryresearchopen,questionvalue,AMS11]theoremerdos_409.parts.i(n:ℕ)(hn:0<n):IsLeast{i|(φ·+1)^[i]n|>.Prime}(erdos_409.parts.i.answern):=n:ℕhn:0<n⊢ IsLeast{i|Nat.Prime((funx↦φx+1)^[i]n)}(i.answern)All goals completed! 🐙
If $n > 0$, then the iteration $n\mapsto\phi(n) + 1$ necessarily
reaches a prime.
neg.inrn:ℕih:∀m<n,0<m→∃i,Nat.Prime((funx↦φx+1)^[i]m)hn:0<nhp:¬Nat.Primenh1:1<nhlt:φn<nhne:φn≠n-1hdec:φn+1<nhpos:0<φn+1i:ℕhi:Nat.Prime((funx↦φx+1)^[i](φn+1))⊢ Nat.Prime((funx↦φx+1)^[i](φn+1))exacthiAll 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.deferdos_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))$?
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))$?
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))$?
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.@[categoryresearchopen,questionvalue,AMS11]theoremerdos_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.answern):=byn:ℕhn:n>1hterm:∃i,Nat.Prime((funx↦(σ1)x-1)^[i]n)⊢ IsLeast{i|Nat.Prime((funx↦(σ1)x-1)^[i]n)}(sigma.answern)sorryAll 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).
@[categoryresearchopen,AMS11]theoremerdos_409.variants.sigma_termination(n:ℕ)(hn:n>1):∃i,(σ1·-1)^[i]n|>.Prime:=byn:ℕhn:n>1⊢ ∃i,Nat.Prime((funx↦(σ1)x-1)^[i]n)sorryAll goals completed! 🐙-- Formalisation note: See the above formalisation note for the rationale-- for including asymptotic variantsdeferdos_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))$?
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))$?
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))$?