21
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ $n=2^{775}3^{310}7^{155}$ $\endgroup$ – Kenny Lau May 7 '16 at 17:41
  • 3
    $\begingroup$ $f(2x)=f(x)+1{}$ $\endgroup$ – Kenny Lau May 7 '16 at 17:42
  • 4
    $\begingroup$ The biggest divisor of $2x$ is always $x$. $\endgroup$ – Kenny Lau May 7 '16 at 17:44
  • 2
    $\begingroup$ 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 ) . $\endgroup$ – DeltaWeb May 7 '16 at 17:46
  • 2
    $\begingroup$ $\forall x\in\mathbb N,\ x\not\equiv0\mbox{ (mod 2)},\ f(3x)=f(2x)+1=f(x)+2$ $\endgroup$ – Kenny Lau May 7 '16 at 17:46
36
$\begingroup$

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.

$\endgroup$
  • 9
    $\begingroup$ +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! $\endgroup$ – rubik May 8 '16 at 6:56
  • 5
    $\begingroup$ What the heck is that program $\endgroup$ – YoTengoUnLCD May 10 '16 at 4:15
  • 1
    $\begingroup$ @YoTengoUnLCD That's nothing :) This program does the exact same thing with significantly less readability! $\endgroup$ – caird coinheringaahing Apr 12 '18 at 23:29
  • 1
    $\begingroup$ @cairdcoinheringaahing but mine actually finishes... $\endgroup$ – Kenny Lau Apr 13 '18 at 1:38
14
$\begingroup$

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

$\endgroup$
8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – orlp May 9 '16 at 23:00
  • $\begingroup$ @orlp Oops, they should be $+$s, not $\cdot$s. $\endgroup$ – MCT May 10 '16 at 3:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.