How to solve this algorithmic math olympiad problem?

Question

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.

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

Answer 2

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

Answer 3

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