Successive Totients

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

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

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

Details and assumptions

  • As an explicit example, here's how you'd find f(5)f(5): ϕ(5)=4ϕ(ϕ(5))=2ϕ(ϕ(ϕ(5)))=1\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 55 to get the number 11, so f(5)=3f(5)=3.

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

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

×

Problem Loading...

Note Loading...

Set Loading...