<s>[INST] Which numbers result in a chain other than $2 \to 0$? Let $n$ be a natural number and $k$ the number of its divisors. Calculate $n-k$, then repeat this procedure by taking $n-k$ as the starting value. If you do this repeatedly, which numbers results in chains other than $2 \to 0$?
I found this problem in the exam prep questions my teacher gave us, so I assume there's a not-so-complicated solution. I tried some small values like $1, 3, 5, 7$ and they seem to give us different chains. However, I don't know how to go about proving that all other numbers beyond a point go to $2 \to 0$. I tried splitting the problem into cases where $n$ has $1, 2, 3,...$ prime factors but that lead nowhere. Any ideas would be appreciated.
 [/INST] Let us denote the iteration function with $f(n) = n - d(n)$, where $d(n)$ is the number of divisors of $n$.
For $n \ge 3$ is $1 \le f(n) \le n-2$, so that the iteration  $n, f(n), f(f(n)), \ldots$ is strictly decreasing until it reaches either $1$ or $2$. Let $t(n)$ be this “terminal” non-zero number in the chain starting at $n$.
We can show that $t(n) = 1$ only for $n=1, 3, 4, 5, 7, 8$, and $t(n) = 2$ for all other starting values $n$.
As it turns out, it suffices to compute $t(n)$ for all starting values in the range $1 \le n \le 15$:
$$
\begin{array}{c|cccccccccccccccc}
n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ \hline
f(n) & 0 & 0 & 1 & 1 & 3 & 2 & 5 & 4 & 6 & 6 & 9 & 6 & 11 & 10 & 11  \\
t(n) & \boxed{1} & 2 & \boxed{1} & \boxed{1} & \boxed{1} & 2 & \boxed{1} & \boxed{1} & 2 & 2 & 2 & 2 & 2 & 2 & 2 
\end{array}
$$
It remains to show that $t(n) = 2$ for $n \ge 16$: For these $n$ is $d(n) < n/2$ (see for example Upper limit for the Divisor function), and therefore $f(n) > n/2$. It follows that the iteration $n, f(n), f(f(n)), \ldots$ must eventually reach a number $m$ in the range $9 \ldots 15$. Then $t(n) = t(m) = 2$.
</s>