# 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.

×

Problem Loading...

Note Loading...

Set Loading...