How to solve this algorithmic math olympiad problem?

Solution 1:

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.

Solution 2:

$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.