A problem of Finucane. One can also ask similar questions about $n\mapsto \sigma(n)-1$: do iterates of this always reach a prime? If so, how soon? (It is easily seen that iterates of this cannot reach the same prime infinitely often, since they are non-decreasing.)

This problem is somewhat ambiguously phrased. Let $F(n)$ count the number of iterations of $n\mapsto \phi(n)+1$ before reaching a prime. The number of iterations required is A039651 in the OEIS.

Cambie notes in the comments that $F(n)=o(n)$ is trivial, and $F(n)=1$ infinitely often. Presumably the intended question is to find 'good' upper bounds for $F(n)$.

This is discussed in problem B41 of Guy's collection [Gu04].

View the LaTeX source

This page was last edited 20 December 2025.