Ułamkowa łamigłówka
To jest łamigłówka zarówno z tagiem komputer-puzzle, jak i znacznikiem braku komputerów .
Mamy następującą listę pięciu ułamków:
$$11/5, 30/77, 1/11, 21/2, 5/7.$$
Zaczynając od liczby całkowitej $x$, wykonujemy następującą operację: na każdym kroku pomnóż $x$ przez pierwszy ułamek (od lewej do prawej) na powyższej liście, co daje wynik w postaci liczby całkowitej.
Jeśli na liście nie ma takiego ułamka, procedura kończy się i wartość $x$ to wynik końcowy.
Przykład: zaczynając od $x = 2$
pierwszy krok: pomnóż to przez $21/2$, co daje $21$.
drugi krok: pomnóż to przez $5/7$, co daje $15$.
trzeci krok: pomnóż to przez $11/5$, co daje $33$.
czwarty krok: pomnóż przez $1/11$, co daje $3$.
Widzimy to $x = 3$ to wynik końcowy, jako pomnożenie $3$ przez którąkolwiek z pięciu ułamków dałoby wynik inny niż całkowity.
Pytanie: jeśli zaczniemy od $x = 2^{1234567}$, więc jakie będą ostatnie trzy cyfry wyniku końcowego?
Uwaga:
Jest to do pewnego stopnia dobrze znane i celowo nie wymieniam nazwy, ponieważ powinno być na tyle proste, że do jego rozwiązania nie jest potrzebna dodatkowa wiedza.
Oczywiście możesz podać imię i nazwisko w swojej odpowiedzi!
Odpowiedzi
Obserwujemy to
tylko jedna frakcja ma mianownik 2
Ponieważ mamy x = 2 ^ 1234567, możemy spróbować to podłączyć. Aby ułatwić sprawę, użyjemy rozłożenia liczb na czynniki pierwsze.
Najpierw pomnożymy przez 21/2, otrzymując 2 ^ 1234566 * 3 * 7. Ponieważ wszystkie ułamki przed 21/2 mają czynnik pierwszy inny niż 2, 3 lub 7, wiemy, że funkcja będzie nadal mnożyć przez 21/2 dopóki nie zostaną żadne współczynniki 2. To daje nam 3 ^ 1234567 * 7 ^ 1234567.
Kolejny,
mnożymy przez 5/7. Ponieważ pierwszy ułamek na liście ma mianownik 5, wiemy, że za każdym razem, gdy pomnożymy przez 5/7, zasadniczo pomnożymy przez 11/7. Mnożymy i otrzymujemy 3 ^ 1234567 * 7 ^ 1234566 * 11. 30/77 to następny ułamek, przez który należy pomnożyć. Otrzymujemy 2 * 3 ^ 1234568 * 5 * 7 ^ 1234565. Mnożenie przez 11/5 daje nam 2 * 3 ^ 1234568 * 7 ^ 1234565 * 11.
Zauważamy to
ponieważ mamy tak dużą liczbę 7s, będziemy mnożyć przez 30/77 i 11/5, aż skończy nam się 7s. Zdajemy sobie sprawę, że za każdym razem, gdy liczba 7 zmniejsza się o 1, liczba 2 wzrasta o 1, a liczba 3 wzrasta o 1. Zwiększamy liczbę czynników 2 i 3 o 1234565 i usuwamy wszystkie czynniki 7, aby otrzymać 2 ^ 1234566 * 3 ^ 2469133 * 11. Mnożymy przez 1/11, aby usunąć współczynnik 11 i otrzymujemy 2 ^ 1234566 * 3 ^ 2469133.
To pozostawia nas w tym samym miejscu, co początek, z wyjątkiem
mamy kilka współczynników 3, a liczba czynników 2 zmniejszyła się o 1.
Ponieważ żaden z mianowników nie ma współczynnika 3,
zrobimy to samo co poprzednio, tylko mniejszą liczbę razy. Eliminacja wszystkich dwójek daje nam 3 ^ 3703699 * 7 ^ 1234566. Mnożymy przez 5/7, a następnie 11/5, aby otrzymać 3 ^ 3703699 * 7 ^ 1234565 * 11. Dodajemy z powrotem potęgi 2 i 3 oraz usuwamy wszystkie potęgi 7 i jedną potęgę 11, aby otrzymać 2 ^ 1234565 * 3 ^ 4938264.
Zauważamy to
za pierwszym razem potęga 3 wzrosła o (1234567 + 1234566), a tym razem potęga 3 wzrosła o (1234566 + 1234565). Oznacza to, że dla potęgi 2, potęga 3 wzrośnie o (2x-1). Oznacza to, że potęga 3 będzie$\sum_{i=1}^{1234567} 2i-1$ Możemy użyć właściwości sumowania, aby uzyskać $2*\sum_{i=1}^{1234567} i - 1234567$. Wiemy, że suma pierwszego$n$ dodatnimi liczbami całkowitymi jest $\frac{n*(n+1)}{2}$, więc $\sum_{i=1}^{1234567} i = 1234567*1234568/2 = 762078456028$, więc $2*\sum_{i=1}^{1234567} i - 1234567 = 1524155677489$
Widzimy to
ostateczna odpowiedź to 3 ^ 1524155677489, a ponieważ ostatnie 3 cyfry 3 ^ x powtarzają się co 100 razy, wystarczy przyjąć potęgę 3 (mod 100), czyli 89.
Oznacza to, że musimy znaleźć tylko ostatnie 3 cyfry
3 ^ 89.
Wiemy, że ostatnie 3 cyfry
3 ^ 10 to 049,
co oznacza ostatnie 3 cyfry
3 ^ 20 to tylko ostatnie 3 cyfry 49 ^ 2 lub 401,
co oznacza ostatnie 3 cyfry
3 ^ 40 to tylko ostatnie 3 cyfry 401 ^ 2 lub 801,
co oznacza ostatnie 3 cyfry
3 ^ 80 to tylko ostatnie 3 cyfry 801 ^ 2 lub 601,
co oznacza ostatnie 3 cyfry
3 ^ 89 to tylko ostatnie 3 cyfry liczby 601 * (ostatnie 3 cyfry 3 ^ 9).
Wiemy, że ostatnie 3 cyfry
3 ^ 9 to tylko 683, co oznacza, że ostatnie 3 cyfry 3 ^ 89 to ostatnie 3 cyfry 601 * 683, czyli 483.
Oznacza to, że nasza ostateczna odpowiedź brzmi
483.
Zastrzeżenie: moje obliczenia są nieco bałaganiarskie, a pojedynczy błąd w obliczeniach spowodowałby, że cała odpowiedź byłaby błędna, ale ogólne rozwiązanie powinno nadal być poprawne.
Nie chcę uchodzić za snobistę, ale udowodnienie / obliczenie czegoś w sposób ekonomiczny ma wartość. Zróbmy więc drugą połowę (obliczenie ostatnich trzech cyfr niesamowicie dużej liczby całkowitej) dowodu. Najpierw wyprowadzamy$3^{100}\equiv 1 \mod 1000$ (bez użycia Eulera $\phi$):
zaczynając od $3^5 = 243$ weźmy piątą potęgę jeszcze dwa razy: Ponieważ potrzebujemy tylko trzech ostatnich cyfr, jest to dość proste przy użyciu twierdzenia dwumianowego, ponieważ łatwo zauważyć, że trzeci i wszystkie następne wyrazy są podzielne przez 1000 i dlatego można je zignorować. $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$
Więc to jest ta sama wartość w obu przypadkach. Wnioskujemy, że 3 i 1000 są względnie pierwsze$3^{100} \equiv 1 \mod 1000$
Mając to ustalone, znajdźmy bezbolesny sposób przetwarzania
$3^{89}$. Dzięki temu, co właśnie pokazaliśmy, mamy$3^{89}\equiv \frac 1 {3^{11}} \mod 1000$. Teraz łatwo zgadnąć, że jest odwrotnością$3$ modulo $1000$ jest $-333$, że z $9$ jest $-111$. A zatem:$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$