How to solve this algorithmic math olympiad problem? So, today we had a local contest in my state to find eligible people for the international math olympiad "IMO" ... 
I was stuck with this very interesting algorithmic problem:
Let $n$ be a natural number ≥ 2, we take the biggest divisor of $n$ but it must be different from $n$ itself, subtract it from $n$. We repeat this until we get $1$.
Example: Let $n = 30$. Then we have to subtract its biggest different divisor, that is, 15. So 30 - 15 = 15, now we do the same: 


*

*5 is the biggest divisor for 15, so 15 - 5 = 10

*5 is the biggest divisor for 10, so 10 - 5 = 5 

*1 is the greatest divisor for 5, so 5 - 1 = 4

*2 is the biggest divisor for 4 so 4 - 2 = 2

*1 is the biggest divisor for 2, so 2 - 1 = 1 . 


And we're done ! it took 6 steps to get 1. 
If  $n = 2016^{155}$ how many steps we have to get 1 at the end ?
I'm a programmer, and I used to rock with logical puzzles, but this time I'm completely lost. So please help me.

Firstly, note that: $$n=2^{775}3^{310}7^{155}$$
Let the number of steps to get from $x$ to $1$ be $f(x)$.

Then, note that the biggest divisor of $2x$ is always $x$.
Therefore: $$f(2x)=f(x)+1$$
For example: $$f(30)=f(15)+1$$
Applying to here: $$f(n)=f(3^{310}7^{155})+775$$

Now, when $x$ is not divisible by $2$, the biggest divisor of $3x$ is always $x$.
Therefore: $$f(3x)=f(3x-x)+1=f(2x)+1=f(x)+2$$
For example: $$f(15)=f(5)+2$$
Applying to here: $$f(n)=f(7^{155})+2\times310+775=f(7^{155})+1395$$

Now, where $x$ is not divisible by $2$, $3$, or $5$, the biggest divisor of $7x$ is always $x$.
Therefore: $$f(7x)=f(6x)+1=f(3x)+2=f(x)+4$$
For example: $$f(77)=f(11)+4$$
Applying to here: $$f(n)=f(1)+4\times155+1395=2015$$

Is it just a coincidence?

Extra:
I wrote a program in Pyth to confirm this (takes a while to calculate).
This is for smaller numbers.
I used this to generate $f(x)$ for $x$ from $1$ to $100$.
A quick search returns OEIS A064097.
