How to solve this algorithmic math olympiad problem?
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.
$2016 = 2 * 2 * 2 * 2 * 2 * 3 * 3 * 7$ . Therefore
$2016^{155} = 2^{775} · 3^{310} ·7^{155}$
Now ask yourself: What's the biggest factor of $2^{775}· 3^{310} ·7^{155}$? Obviously it's $2^{774} ·3^{310} ·7^{155}$. Subtract from the original number, and $2^{774}· 3^{310} ·7^{155}$ remains. The same thing will happen exactly $775 $ times, and then you will be left with $3^{310} ·7^{155}$ after $775$ subtractions.
What's the biggest factor of $3^{310}· 7^{155}$? The biggest factor is $3^{309} ·7^{155}$. Subtract this and the remainder is $2 · 3^{309} ·7^{155}$. That again has the largest factor $3^{309} ·7^{155}$. Subtract this again and the remainder is $3^{309} ·7^{155}$. With two subtractions we divided by $3$ . We repeat $310$ times for a total of $620$ subtractions and the remainder is $7^{155}$.
Now the largest divisor is $7^{154}$; subtracting this leaves $6 · 7^{154}$. Now the largest factor is $3 · 7^{154}$ leaving $3 · 7^{154}$. Then the largest factor is again $7^{154}$, leaving first $2 · 7^{154}$ then $7^{154}$. $4$ subtractions to divide by $7$ . We repeat a total of $155$ times, for $620 $subtractions, arriving at $1$ . In Total $775 + 620 + 620 = 2015 $ subtractions.
Note that $(2016)^{155} = 2^{775} \cdot 3^{310} \cdot 7^{155}$.
For the first step, we subtract by $2^{774} \cdot 3^{310} \cdot 7^{155}$ since this is the largest non-trivial divisor.
This gives $2016^{155} - \frac{1}{2} 2016^{155} = \frac{1}{2} 2016^{155}$. We repeat this for the first $775$ steps until we have just $3^{310} \cdot 7^{155}$.
Now, the largest divisor is $3^{309} \cdot 7^{155}$. We subtract now to get $2 \cdot 3^{309} \cdot 7^{155}$. The largest divisor of this is now $3^{309} \cdot 7^{155}$, and subtracting from our result gives $3^{309} \cdot 7^{155}$. It's clear that to get rid of all the threes, we take $2 \cdot 310$ steps.
Finally, now we just have $7^{155}$. It takes $4$ steps to turn this into $7^{154}$ (namely $7$ becomes $6$, $6$ becomes $3$, $3$ becomes $2$, and $2$ becomes $1$) so it takes $4 \cdot 155$ more steps to become $1$.
All in all, this is $2015$ steps.
Remark. The generalization here is clear.
If $n = p_1^{e_1} p_2^{e_2} \dots p_n^{e_n}$ then $f(n) = e_1 f(p_1) + e_2 f(p_2) + \ldots + e_n f(p_n)$.