Define a function $\phi_* : \mathbb{N}_{>0} \rightarrow \mathbb{N}_{>0}$ as follows: $\phi_*(n)$ is the number of times we apply the totient function $\phi$ to $n$ to obtain 1 for the first time (the last restriction is necessary as $\phi(1) = 1$). That is, if $\phi_*(n) = k$, then the LHS of the equation $\phi(\phi(\dots \phi(n) \dots )) = 1$ contains precisely $k$ $\phi$ symbols.
First, it may help to argue that for inputs $\geq 2$, as the output of $\phi$ is both positive and strictly lower than the input, after applying $\phi$ a finite number of times, we eventually must reach $1$. The values of $\phi_*$ itself aren't terribly interesting; it appears to grow roughly logarithmically, which we might expect given its definition.
What is perhaps slightly more interesting is the function $f : \mathbb{N}_{>0} \rightarrow \mathbb{N}_{>0}$ given by $$f(k) = \min \{n \mid \phi_*(n) = k\}$$ That is, $f(k)$ gives the smallest possible $n$ such that it takes $k$ applications of $\phi$ starting from $n$ to reach $1$.
By burning my CPU for some number of hours, I computed the values of $\phi_*(n)$ for $0 \leq n < 100000000$, which gives me the first $27$ values of $f$:
$$\begin{array}{c c c c} f(1) = 2 & f(2) = 3 & f(3) = 5 & f(4) = 11 \\ f(5) = 17 & f(6) = 41 & f(7) = 83 & f(8) = 137 \\ f(9) = 257 & f(10) = 641 & f(11) = 1097 & f(12) = 2329 \\ f(13) = 4369 & f(14) = 10537 & f(15) = 147477 & f(16) = 35209 \\ f(17) = 65537 & f(18) = 140417 & f(19) = 281929 & f(20) = 557057 \\ f(21) = 1114129 & f(22) = 2384897 & f(23) = 4227137 & f(24) = 8978569 \\ f(25) = 16843009 & f(26) = 35946497 & f(27) = 71304257 \end{array}$$
The values of $f$ don't have too many factors, which is to be expected as if there were many factors, the multiplicativity of $\phi$ would lower the value by a lot, leading to fewer $\phi$'s needed to reach 1. As a result, most of the values on this list are prime (aside: all currently known Fermat primes are on the list). However, some are not prime:
$$\begin{array}{c} f(12) = 17 \times 137 \\ f(13) = 17 \times 257 \\ f(14) = 41 \times 257 \\ f(16) = 137 \times 257 \\ f(19) = 257 \times 1097 \\ f(21) = 17 \times 65537 \\ f(24) = 137 \times 65537 \\ f(25) = 257 \times 65537 \end{array}$$
On the other hand, the factors of these products are smaller values of $f$. To some extent, it makes intuitive sense that we are "combining two minimal numbers which satisfy some property to obtain another minimal number which satisfies some property", but I don't find it obvious that this should necessarily be true for all composite values of $f$, which brings me to my question:
Question: Are the values of $f$ necessarily of one of two forms: prime, or products of other prime values of $f$?
Edit: It has been brought to my attention that this sequence has already been studied before, and is in the OEIS as A007755. In particular, the following results have been found:
Shapiro shows that the smallest number is greater than $2^{n-1}$. Catlin shows that if $a(n)$ is odd and composite, then its factors are among the $a(k)$, $k < n$. For example $a(12)$ = $a(5)$ $a(8)$. There is a conjecture that all terms of this sequence are odd.
In the quote, the mentioned $a(n)$ is $f(n - 1)$. Catlin's result (proved in 1970!) answers the part of my question regarding composite values of $f$, and it appears the other part has yet to be solved. Shapiro's work in 1943 is also noteworthy, which studies several properties of $\phi_*$.
Additional observations which may or may not mean anything:
- Very roughly speaking, $f(k + 1) \approx 2f(k)$.
- For every composite value of $f$ in the list above, at least one of the factors is one of the Fermat primes.