For all positive integers , the totient function denotes the number of positive integers coprime to .
It turns out that if we apply the totient function successively on any positive integer , after finitely many operations we get the number . In other words, for all positive integers , there exists a positive integer such that .
For all , let denote the minimum number of times we need to apply the totient function successively on to get the number . Find the last three digits of .
Details and assumptions
As an explicit example, here's how you'd find : Note that we had to apply the totient function three times on to get the number , so .
By convention, .
Just to clarify, this is a computer science problem.