Iterating $n\mapsto\phi(n)+1$ to a prime: iteration count, fibers, and densities (Erdős #409)
Statement
Consider the map $n\mapsto \phi(n)+1$, where $\phi$ is the Euler totient function, and iterate it. For $n$ that eventually reach a prime, let $F(n)$ be the number of iterations of $n\mapsto\phi(n)+1$ needed to first reach a prime. (i) How large can $F(n)$ be — find good upper bounds. (ii) Can infinitely many $n$ reach the same prime? (iii) For a fixed prime $p$, what is the density of the set of $n$ whose iteration first reaches $p$?
Acceptance. FULLY RESOLVES: rigorous answers to the core questions — a proven good upper bound on $F(n)$ (e.g. $F(n)\ll(\log n)^{O(1)}$, or the true order, with proof), together with a proof settling whether infinitely many $n$ reach the same prime and a determination of the density of the fiber of a fixed prime $p$; full written proofs. ADVANCES (each itself checkable): a proven nontrivial upper bound on $F(n)$ strictly stronger than the trivial $F(n)=o(n)$ recorded in the background; a proof that some fixed prime has an infinite fiber (or a proof that every prime's fiber is finite); a rigorous density result for at least one prime $p$; or a reproducible large-scale computation extending OEIS A039651 that reports records of $F(n)$, the largest fibers observed, and empirical fiber densities, with the code and the range covered. Numerical evidence counts as ADVANCES only when delivered as reproducible code plus the certified range. Deliver the proof and/or the search code with the attained range and measured statistics.
Background
A problem of Finucane, recorded in Erdős–Graham [ErGr80, p.81] and discussed as problem B41 in Guy [Gu04]; listed as open on erdosproblems.com/409 (fetched 2026-07-13, status 'open', tagged 'number theory | iterated functions'), no prize. The iteration count $F(n)$ is OEIS A039651 (with A229487 a related sequence); a formal statement exists in DeepMind's formal-conjectures Lean library. Bloom notes the phrasing is somewhat ambiguous and that the intended core question is 'good' upper bounds for $F(n)$. Cambie observes in the site comments that $F(n)=o(n)$ is trivial and that $F(n)=1$ holds infinitely often (i.e. $\phi(n)+1$ is prime for infinitely many $n$). A natural companion map, also raised on the page, is $n\mapsto\sigma(n)-1$ (sum of divisors minus one): do its iterates always reach a prime, and how soon? For that map the iterates are non-decreasing, so it cannot reach the same prime infinitely often — unlike the $\phi(n)+1$ map, where the fiber question (ii) is genuinely open. Attacker's tool: large-scale iteration and sieving to compute $F(n)$ (extending A039651), locate primes with large fibers, and measure densities empirically, combined with anatomy-of-integers / sieve arguments to prove upper bounds on $F(n)$ and to decide the infinitude and density questions.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #409 (T. F. Bloom) | website |
| REF-02 | OEIS A039651 — iterations of phi(n)+1 needed to reach a prime | website |
| REF-03 | OEIS A229487 — sequence related to iterating phi(n)+1 | website |
| REF-04 | DeepMind formal-conjectures — Lean statement of Erdős #409 | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.