A fraction puzzle

Question

This is a puzzle with both the computer-puzzle tag and the no-computers tag.

---

We have the following list of five fractions:

$$11/5, 30/77, 1/11, 21/2, 5/7.$$

Starting with an integer $x$, we perform the following operation: at each step, multiply $x$ by the first fraction (from left to right) in the above list that gives an integer result.

If there is no such fraction in the list, then the procedure ends and the value of $x$ is the final result.

---

Example: starting with $x = 2$

• the first step: multiply it by $21/2$, which gives $21$.

• the second step: multiply it by $5/7$, which gives $15$.

• the third step: multiply it by $11/5$, which gives $33$.

• the fourth step: multiply it by $1/11$, which gives $3$.

We see that $x = 3$ is the final result, as multiplying $3$ by any of the five fractions would give non-integer result.

---

Question: if we start with $x = 2^{1234567}$, then what will be the last three digits of the final result?

---

Remark:

This is to some extent well-known, and I intentionally don't mention the name, as it should be simple enough that no extra knowledge is needed to solve it.

Of course, you are welcome to point out the name in your answer!

Answer 1

We observe that

only one fraction has a denominator of 2

As we have x = 2^1234567, we can try to plug it in. We will use the prime factorization of the numbers to make things easier.

We first multiply by 21/2, getting 2^1234566 * 3 * 7. Because all the fractions before 21/2 have a prime factor other than 2, 3, or 7, we know that the function will continue multiplying by 21/2 until there are no factors of 2 left. This leaves us with 3^1234567 * 7^1234567.

Next,

we multiply by 5/7. Because the first fraction in the list has a denominator of 5, we know that anytime we multiply by 5/7 we will essentially be multiplying by 11/7. We multiply and get 3^1234567 * 7^1234566 * 11. 30/77 is the next fraction to multiply by. We end up with 2 * 3^1234568 * 5 * 7^1234565. Multiplying by 11/5 gives us 2 * 3^1234568 * 7^1234565 * 11.

We notice that

because we have such a large amount of 7s, we will keep on multiplying by 30/77 and 11/5 until we run out of 7s. We realize that every time the number of 7s decreases by 1, the number of 2s increases by 1 and the number of 3s increases by 1. We increase the number of factors of 2 and 3 by 1234565 and remove all the factors of 7 to get 2^1234566 * 3^2469133 * 11. We multiply by 1/11 to remove the factor of 11 and get 2^1234566 * 3^2469133.

This leaves us in the same place as the beginning, except

we have a bunch of factors of 3 and the number of factors of 2 decreased by 1.

Because none of the denominators have a factor of 3,

we will do the same thing as before, just a smaller number of times. Eliminating all the 2s gives us 3^3703699 * 7^1234566. We multiply by 5/7 and then 11/5 to get 3^3703699 * 7^1234565 * 11. We add back the powers of 2 and 3 and remove all the powers of 7 and the one power of 11 to get 2^1234565 * 3^4938264.

We notice that

the first time the power of 3 increased by (1234567+1234566), and this time the power of 3 increased by (1234566+1234565). This means that for a power of 2, it will increase the power of 3 by (2x-1). This means the power of 3 will be $\sum_{i=1}^{1234567} 2i-1$ We can use summation properties to get $2*\sum_{i=1}^{1234567} i - 1234567$. We know that the sum of the first $n$ positive integers is $\frac{n*(n+1)}{2}$, so $\sum_{i=1}^{1234567} i = 1234567*1234568/2 = 762078456028$, so $2*\sum_{i=1}^{1234567} i - 1234567 = 1524155677489$

We see that

the final answer is 3^1524155677489, and because the last 3 digits of 3^x repeat every 100 times, we only need to take the power of 3 (mod 100), which is 89.

This means we just need to find the last 3 digits of

3^89.

We know that the last 3 digits of

3^10 are 049,

which means the last 3 digits of

3^20 are just the last 3 digits of 49^2, or 401,

which means the last 3 digits of

3^40 are just the last 3 digits of 401^2, or 801,

which means the last 3 digits of

3^80 are just the last 3 digits of 801^2, or 601,

which means the last 3 digits of

3^89 are just the last 3 digits of 601 * (the last 3 digits of 3^9).

We know that the last 3 digits of

3^9 are just 683, which means the last 3 digits of 3^89 are the last 3 digits of 601*683, which are 483.

This means our final answer is

483.

Disclaimer: My calculations are a bit messy, and a single miscalculation would make the whole answer wrong, but the general solution should still be correct.

Answer 2

I don't want to come across as snobbish but there is value in proving/calculating something economically. So let's do the second half (computing the last three digits of an insanely high integer power) of the proof properly. First, we derive $3^{100}\equiv 1 \mod 1000$ (without using Euler $\phi$):

starting from $3^5 = 243$ let's take the fifth power two more times: Since we only need the last three digits this is quite simple using binomial theorem because it is easily seen that the third and all following terms are divisible by 1000 and can therefore be ignored. $3^{25} \equiv (240+3)^5 \equiv 243 + 5\times 81\times 240 + 10\times 27\times 240^2 + ... \equiv 443 \mod 1000$ $3^{125} \equiv (440+3)^5 \equiv 243 + 5\times 81\times 440 \equiv 443 \mod 1000$
So that is the same value in both cases. As 3 and 1000 are relatively prime we conclude $3^{100} \equiv 1 \mod 1000$

With that established let us find a painless way of computing

$3^{89}$. By what we just have shown we have $3^{89}\equiv \frac 1 {3^{11}} \mod 1000$. Now, it is easy to guess that the inverse of $3$ modulo $1000$ is $-333$, that of $9$ is $-111$. Thus: $3^{89}\equiv 3^{-11} \equiv 333\times 111^5 \equiv 333\times \left ( 1 + 5 \times 110 \right ) \equiv 333 \times 551 \equiv 333 + 650 + 500 \equiv 483 \mod 1000$