Math Headache

It’s the middle of the summer. Little Z spent most of his holidays sunbathing on the sea. He got very bored after being for a week on the sea already, and thought that training his mind a little bit would solve this boredom. He got very happy when the woman at the reception told him that the hotel had a library, so he rushed there to take a book. Unfortunately, the only book left was a math book by H.N.Shapiro, from the far year of 1943.

He took that book so he could read anything. The book seemed very interesting. It had lot of weird functions and tasks, and Little Z liked it very much. He was mostly interested in the Euler’s function. It seemed to tell for the positive integer N how many positive integers K there are, such that K is smaller than N and GCD(K,N)=1.

Little Z thought it would be fun to take one number, and calculate it’s number of divisors. So he took 11, and calculated that it would be 10 (1,2,3,4,5,6,7,8,9,10). He then took the 10 and did the same, and got 4 (1,3,7,9), did that with 4 and got 2 (1,3). He chose to stop at 2, and try another number. He took 25, he got 20, 8, 4 and ended up at 2 again ! !

He thought that was very cool, so he made a function f(N) such that for the given number N it calculates the number of times you have to call euler’s function to get 2. So, e.g. f(11)=3, f(25)=4, f(8)=2 etc. He wanted to find f(N) for every number, and noticed that f(N)=1 appears last time at N=6, f(N)=3 at N=54 etc. He made a function g(N)=K that tells for the number N the highest number K at which it appears as the value of the function f… simply said g(N)=K <=> f(K)=N and for L>K, f(L)>N.

He got a headache from the task, so he asked you to write a program that calculates g(x) for a given number x.

Just to break it down a little bit:

value|1|2|3|4|5|6|7|8|9|10|11|12|13|14|15|16|17|18|19|20
euler|1|1|2|2|4|2|6|4|6| 4|10| 4|12| 6| 8| 8|16|06|18| 8
f____|/|/|1|1|2|1|2|2|2| 2| 3| 2| 3| 2| 3| 3| 4| 2| 3| 3