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

• $n=2^{775}3^{310}7^{155}$ – Kenny Lau May 7 '16 at 17:41
• $f(2x)=f(x)+1{}$ – Kenny Lau May 7 '16 at 17:42
• The biggest divisor of $2x$ is always $x$. – Kenny Lau May 7 '16 at 17:44
• I'd love if you could write an answer explaining your solution in a well and detailed way . (please don't use those fancy math symbols, I'm still at high school, and we didn't learn yet about them ) . – DeltaWeb May 7 '16 at 17:46
• $\forall x\in\mathbb N,\ x\not\equiv0\mbox{ (mod 2)},\ f(3x)=f(2x)+1=f(x)+2$ – Kenny Lau May 7 '16 at 17:46

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.

• +1 For the clear explanation. And wow a program in Pyth. At first I thought it was a typo for Python, but then... Until now I had only seen it on codegolf.SE! – rubik May 8 '16 at 6:56
• What the heck is that program – YoTengoUnLCD May 10 '16 at 4:15
• @YoTengoUnLCD That's nothing :) This program does the exact same thing with significantly less readability! – caird coinheringaahing Apr 12 '18 at 23:29
• @cairdcoinheringaahing but mine actually finishes... – Kenny Lau Apr 13 '18 at 1:38

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

• Your generalization is incorrect for $f(6)$, because $f(6) = f(2) \cdot f(3) = 1 \cdot 2 = 2$, but the correct answer is 3 (6 -> 3 -> 2 -> 1). – orlp May 9 '16 at 23:00
• @orlp Oops, they should be $+$s, not $\cdot$s. – MCT May 10 '16 at 3:28