Teka-teki pecahan
Ini adalah teka -teki dengan tag puzzle komputer dan tag tanpa komputer .
Kami memiliki daftar lima fraksi berikut:
$$11/5, 30/77, 1/11, 21/2, 5/7.$$
Dimulai dengan integer $x$, kami melakukan operasi berikut: di setiap langkah, kalikan $x$ dengan pecahan pertama (dari kiri ke kanan) dalam daftar di atas yang memberikan hasil bilangan bulat.
Jika tidak ada pecahan seperti itu dalam daftar, maka prosedur berakhir dan nilai $x$ adalah hasil akhirnya.
Contoh: dimulai dengan $x = 2$
langkah pertama: kalikan dengan $21/2$, yang memberikan $21$.
langkah kedua: kalikan dengan $5/7$, yang memberikan $15$.
langkah ketiga: kalikan dengan $11/5$, yang memberikan $33$.
langkah keempat: kalikan dengan $1/11$, yang memberikan $3$.
Kami melihat itu $x = 3$ adalah hasil akhir, sebagai perkalian $3$ dengan salah satu dari lima pecahan akan memberikan hasil non-integer.
Pertanyaan: jika kita mulai dengan $x = 2^{1234567}$, lalu berapa tiga digit terakhir dari hasil akhir?
Ucapan:
Ini sampai batas tertentu terkenal, dan saya sengaja tidak menyebutkan namanya, karena harus cukup sederhana sehingga tidak diperlukan pengetahuan tambahan untuk menyelesaikannya.
Tentu saja, Anda dipersilakan untuk menyebutkan nama dalam jawaban Anda!
Jawaban
Kami mengamati itu
hanya satu pecahan yang memiliki penyebut 2
Karena kita memiliki x = 2 ^ 1234567, kita dapat mencoba memasukkannya. Kita akan menggunakan faktorisasi prima dari bilangan tersebut untuk mempermudah.
Kita pertama kali mengalikan dengan 21/2, mendapatkan 2 ^ 1234566 * 3 * 7. Karena semua pecahan sebelum 21/2 memiliki faktor prima selain 2, 3, atau 7, kita tahu bahwa fungsinya akan terus mengalikan dengan 21/2 sampai tidak ada faktor 2 yang tersisa. Ini menyisakan 3 ^ 1234567 * 7 ^ 1234567 untuk kita.
Lanjut,
kita kalikan dengan 5/7. Karena pecahan pertama dalam daftar memiliki penyebut 5, kita tahu bahwa setiap kali kita mengalikan dengan 5/7, pada dasarnya kita akan mengalikannya dengan 11/7. Kita mengalikan dan mendapatkan 3 ^ 1234567 * 7 ^ 1234566 * 11. 30/77 adalah pecahan berikutnya yang akan dikalikan. Kami berakhir dengan 2 * 3 ^ 1234568 * 5 * 7 ^ 1234565. Mengalikan dengan 11/5 menghasilkan 2 * 3 ^ 1234568 * 7 ^ 1234565 * 11.
Kami memperhatikan itu
karena kita memiliki jumlah 7 yang besar, kita akan terus mengalikannya dengan 30/77 dan 11/5 hingga kita kehabisan 7. Kami menyadari bahwa setiap kali angka 7 berkurang 1, angka 2 bertambah 1 dan angka 3 bertambah 1. Kami menambah jumlah faktor 2 dan 3 dengan 1234565 dan menghapus semua faktor 7 untuk mendapatkan 2 ^ 1234566 * 3 ^ 2469133 * 11. Kita mengalikan dengan 1/11 untuk menghilangkan faktor dari 11 dan mendapatkan 2 ^ 1234566 * 3 ^ 2469133.
Ini meninggalkan kita di tempat yang sama seperti awal, kecuali
kami memiliki sekelompok faktor 3 dan jumlah faktor 2 berkurang 1.
Karena tidak ada penyebut yang memiliki faktor 3,
kita akan melakukan hal yang sama seperti sebelumnya, hanya beberapa kali. Menghilangkan semua angka 2 memberi kita 3 ^ 3703699 * 7 ^ 1234566. Kita mengalikan dengan 5/7 lalu 11/5 untuk mendapatkan 3 ^ 3703699 * 7 ^ 1234565 * 11. Kita menambahkan kembali pangkat 2 dan 3 dan menghapus semua pangkat 7 dan satu pangkat 11 untuk mendapatkan 2 ^ 1234565 * 3 ^ 4938264.
Kami memperhatikan itu
pertama kali kekuatan 3 meningkat sebesar (1234567 + 1234566), dan kali ini kekuatan 3 meningkat sebesar (1234566 + 1234565). Artinya untuk pangkat 2, akan menambah pangkat 3 sebesar (2x-1). Ini berarti kekuatan 3 akan menjadi$\sum_{i=1}^{1234567} 2i-1$ Kita bisa menggunakan properti penjumlahan untuk mendapatkan $2*\sum_{i=1}^{1234567} i - 1234567$. Kita tahu itu jumlah yang pertama$n$ bilangan bulat positif adalah $\frac{n*(n+1)}{2}$, jadi $\sum_{i=1}^{1234567} i = 1234567*1234568/2 = 762078456028$, jadi $2*\sum_{i=1}^{1234567} i - 1234567 = 1524155677489$
Kami melihat itu
jawaban akhirnya adalah 3 ^ 1524155677489, dan karena 3 digit terakhir dari 3 ^ x berulang setiap 100 kali, kita hanya perlu mengambil pangkat 3 (mod 100), yaitu 89.
Artinya, kita hanya perlu mencari 3 digit terakhir dari
3 ^ 89.
Kita tahu bahwa 3 digit terakhir
3 ^ 10 adalah 049,
yang berarti 3 digit terakhir
3 ^ 20 hanyalah 3 digit terakhir dari 49 ^ 2, atau 401,
yang berarti 3 digit terakhir
3 ^ 40 hanyalah 3 digit terakhir dari 401 ^ 2, atau 801,
yang berarti 3 digit terakhir
3 ^ 80 hanyalah 3 digit terakhir dari 801 ^ 2, atau 601,
yang berarti 3 digit terakhir
3 ^ 89 hanyalah 3 digit terakhir dari 601 * (3 digit terakhir dari 3 ^ 9).
Kita tahu bahwa 3 digit terakhir
3 ^ 9 hanyalah 683, yang berarti 3 digit terakhir dari 3 ^ 89 adalah 3 digit terakhir dari 601 * 683, yaitu 483.
Artinya jawaban akhir kita adalah
483.
Penafian: Perhitungan saya agak berantakan, dan satu kesalahan perhitungan akan membuat keseluruhan jawaban menjadi salah, tetapi solusi umum tetap harus benar.
Saya tidak ingin dianggap sombong tetapi ada nilai dalam membuktikan / menghitung sesuatu secara ekonomis. Jadi mari kita lakukan paruh kedua (menghitung tiga digit terakhir dari pangkat bilangan bulat yang sangat tinggi) dari pembuktian dengan benar. Pertama, kami menurunkan$3^{100}\equiv 1 \mod 1000$ (tanpa menggunakan Euler $\phi$):
mulai dari $3^5 = 243$ mari kita ambil pangkat kelima dua kali lagi: Karena kita hanya memerlukan tiga digit terakhir, ini cukup sederhana menggunakan teorema binomial karena mudah dilihat bahwa suku ketiga dan semua suku berikut habis dibagi 1000 dan oleh karena itu dapat diabaikan. $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$
Jadi itu adalah nilai yang sama dalam kedua kasus tersebut. Karena 3 dan 1000 relatif prima, kami menyimpulkan$3^{100} \equiv 1 \mod 1000$
Dengan itu, mari kita temukan cara komputasi yang tidak menyakitkan
$3^{89}$. Dengan apa yang baru saja kami tunjukkan, kami miliki$3^{89}\equiv \frac 1 {3^{11}} \mod 1000$. Sekarang, mudah untuk menebak bahwa kebalikan dari$3$ modulo $1000$ aku s $-333$, itu dari $9$ aku s $-111$. Jadi:$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$