Problem 409

../

---

Statement. How many iterations of $n\mapsto \phi(n)+1$ are needed before a prime is reached? Can infinitely many $n$ reach the same prime? What is the density of $n$ which reach any fixed prime?

Status. Open.

Source. erdosproblems.com/409, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #409, https://www.erdosproblems.com/409.

References.

• [Gu04] Guy, Richard K., Unsolved problems in number theory, third edition, Problem Books in Mathematics, Springer (2004), xviii+437 pp.; B41 "Iterations of $\phi$ and $\sigma$", p. 148: Finucane's iteration of $\phi(n)+1$, the number of steps to a prime, the distribution of the $n$ whose sequences end in a given prime $p$, and whether 5, 8, 10, 12 are the only numbers leading to 5 and 7, 9, 14, 15, 16, 18, 20, 24, 30 the only ones leading to 7. Library home: guy_2004_unsolved_problems_number_theory.

Formalization. Statement in formal-conjectures.

Progress

Not yet compiled.

Known Results

Not yet compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

• guy_2004_unsolved_problems_number_theory