25
$\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$
9
  • 5
    $\begingroup$ $n=2^{775}3^{310}7^{155}$ $\endgroup$
    – Kenny Lau
    May 7, 2016 at 17:41
  • 3
    $\begingroup$ $f(2x)=f(x)+1{}$ $\endgroup$
    – Kenny Lau
    May 7, 2016 at 17:42
  • 4
    $\begingroup$ The biggest divisor of $2x$ is always $x$. $\endgroup$
    – Kenny Lau
    May 7, 2016 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, 2016 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, 2016 at 17:46

3 Answers 3

39
$\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$
5
  • 11
    $\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, 2016 at 6:56
  • 5
    $\begingroup$ What the heck is that program $\endgroup$ May 10, 2016 at 4:15
  • 2
    $\begingroup$ @YoTengoUnLCD That's nothing :) This program does the exact same thing with significantly less readability! $\endgroup$ Apr 12, 2018 at 23:29
  • 1
    $\begingroup$ @cairdcoinheringaahing but mine actually finishes... $\endgroup$
    – Kenny Lau
    Apr 13, 2018 at 1:38
  • $\begingroup$ Glad to see my language in the wild $\endgroup$
    – isaacg
    Jul 12 at 19:33
16
$\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$
9
$\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$
2
  • $\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, 2016 at 23:00
  • $\begingroup$ @orlp Oops, they should be $+$s, not $\cdot$s. $\endgroup$
    – MCT
    May 10, 2016 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.