分数パズル
これは、computer-puzzleタグとno-computersタグの両方を使用したパズルです。
次の5つの分数のリストがあります。
$$11/5, 30/77, 1/11, 21/2, 5/7.$$
整数で始まる $x$、次の操作を実行します。各ステップで、乗算します。 $x$ 整数の結果を与える上記のリストの最初の分数（左から右へ）。
リストにそのような分数がない場合、手順は終了し、の値は $x$ 最終結果です。
例：で始まる $x = 2$
最初のステップ：それを掛ける $21/2$、 $21$。
2番目のステップ：それを掛ける $5/7$、 $15$。
3番目のステップ：それを掛ける $11/5$、 $33$。
4番目のステップ：それを掛ける $1/11$、 $3$。
わかります $x = 3$ 乗算としての最終結果です $3$ 5つの分数のいずれかによって、非整数の結果が得られます。
質問：私たちが $x = 2^{1234567}$、では、最終結果の最後の3桁はどうなりますか？
リマーク：
これはある程度よく知られていますが、名前を意図的に言及することはありません。名前を解決するために追加の知識が必要ないほど単純である必要があるためです。
もちろん、あなたはあなたの答えの中で名前を指摘することを歓迎します！
回答
私たちはそれを観察します
分母が2の分数は1つだけです
x = 2 ^ 1234567であるため、プラグインを試みることができます。数値の素因数分解を使用して、作業を簡単にします。
最初に21/2を掛けて、2 ^ 1234566 * 3 * 7を取得します。21/ 2より前のすべての分数は2、3、または7以外の素因数を持っているため、関数は21/2を掛け続けることがわかります。 2の因数がなくなるまで。これにより、3 ^ 1234567 * 7 ^ 1234567が残ります。
次、
5/7を掛けます。リストの最初の分数の分母は5であるため、5/7を掛けるときはいつでも、基本的に11/7を掛けることになります。乗算すると、3 ^ 1234567 * 7 ^ 1234566 * 11が得られます。30/ 77は次に乗算する分数です。最終的に2 * 3 ^ 1234568 * 5 * 7 ^ 1234565になります。11/5を掛けると、2 * 3 ^ 1234568 * 7 ^ 1234565 * 11になります。
私たちはそれに気づきます
7がたくさんあるので、7がなくなるまで、30/77と11/5を掛け続けます。7の数が1減少するたびに、2の数が1増加し、3の数が1増加することがわかります。2と3の因子の数を1234565ずつ増やし、7のすべての因子を削除して取得します。 2 ^ 1234566 * 3 ^ 2469133 * 11. 1/11を掛けて11の因数を削除し、2 ^ 1234566 * 3 ^ 2469133を取得します。
これにより、最初と同じ場所に残りますが、
3の因子がたくさんあり、2の因子の数が1減少しました。
分母のどれも3の因数を持っていないので
以前と同じことを行いますが、回数は少なくなります。2をすべて削除すると、3 ^ 3703699 * 7 ^ 1234566になります。5/7を掛けてから11/5を掛けると、3 ^ 3703699 * 7 ^ 1234565 * 11になります。2と3の累乗を加算し、7の累乗と11の1つの累乗を削除して2 ^ 1234565を取得します。 * 3 ^ 4938264。
私たちはそれに気づきます
初めて3の累乗が（1234567 + 1234566）増加し、今回は3の累乗が（1234566 + 1234565）増加しました。これは、2の累乗の場合、3の累乗が（2x-1）増加することを意味します。これは、3の累乗が$\sum_{i=1}^{1234567} 2i-1$ 合計プロパティを使用して取得できます $2*\sum_{i=1}^{1234567} i - 1234567$。私たちは最初の合計が$n$ 正の整数は $\frac{n*(n+1)}{2}$、 そう $\sum_{i=1}^{1234567} i = 1234567*1234568/2 = 762078456028$、 そう $2*\sum_{i=1}^{1234567} i - 1234567 = 1524155677489$
わかります
最終的な答えは3 ^ 1524155677489であり、3 ^ xの最後の3桁は100回ごとに繰り返されるため、3の累乗（mod 100）、つまり89を取得するだけで済みます。
これは、の最後の3桁を見つける必要があることを意味します
3 ^ 89。
の最後の3桁は
3 ^ 10は049、
これは、の最後の3桁を意味します
3 ^ 20は、49 ^ 2の最後の3桁、つまり401であり、
これは、の最後の3桁を意味します
3 ^ 40は、401 ^ 2の最後の3桁、つまり801です。
これは、の最後の3桁を意味します
3 ^ 80は、801 ^ 2の最後の3桁、つまり601です。
これは、の最後の3桁を意味します
3 ^ 89は、601 *の最後の3桁（3 ^ 9の最後の3桁）です。
の最後の3桁は
3 ^ 9は683です。つまり、3 ^ 89の最後の3桁は601 * 683の最後の3桁、つまり483です。
これは私たちの最終的な答えが
483。
免責事項：私の計算は少し面倒で、1回の計算ミスで全体の答えが間違ってしまいますが、一般的な解決策は正しいはずです。
私は卑劣なものとして出くわしたくありませんが、何かを経済的に証明/計算することには価値があります。それでは、証明の後半（めちゃくちゃ高い整数乗の最後の3桁を計算する）を適切に実行しましょう。まず、$3^{100}\equiv 1 \mod 1000$ （オイラーを使用せずに $\phi$）：
から始まる $3^5 = 243$ 五乗をさらに2回取りましょう。最後の3桁だけが必要なので、二項定理を使用すると、3番目以降のすべての項が1000で割り切れるので無視できることが簡単にわかるため、これは非常に簡単です。 $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$
つまり、どちらの場合も同じ値です。3と1000は互いに素なので、結論として$3^{100} \equiv 1 \mod 1000$
それが確立されたら、痛みのないコンピューティング方法を見つけましょう
$3^{89}$。私たちが今示したことによって、私たちは持っています$3^{89}\equiv \frac 1 {3^{11}} \mod 1000$。さて、の逆は簡単に推測できます$3$ モジュロ $1000$ です $-333$、 の $9$ です $-111$。したがって：$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$