# Successive Totients

For all positive integers $$n$$, the totient function $$\phi (n)$$ denotes the number of positive integers $$\leq n$$ coprime to $$n$$.

It turns out that if we apply the totient function successively on any positive integer $$n>1$$, after finitely many operations we get the number $$1$$. In other words, for all positive integers $$n>1$$, there exists a positive integer $$m$$ such that $$\underbrace{\phi ( \phi ( \phi ( \cdots \phi (n ) \cdots )))}_{m \text{ times}}= 1$$.

For all $$n \in \mathbb{N}$$, let $$f(n)$$ denote the minimum number of times we need to apply the totient function successively on $$n$$ to get the number $$1$$. Find the last three digits of $$\displaystyle \sum \limits_{n=1}^{2014} f(n)$$.

Details and assumptions

• As an explicit example, here's how you'd find $$f(5)$$: $\begin{array}{rcl} \phi (5)& = & 4 \\ \phi (\phi (5)) & = & 2 \\ \phi (\phi (\phi (5))) & = & 1 \\ \end{array}$ Note that we had to apply the totient function three times on $$5$$ to get the number $$1$$, so $$f(5)=3$$.

• By convention, $$f(1)=0$$.

• Just to clarify, this is a computer science problem.

×