Ein Bruchteil des Puzzles
Dies ist ein Puzzle mit dem Computer-Puzzle- Tag und dem No-Computer- Tag.
Wir haben die folgende Liste von fünf Fraktionen:
$$11/5, 30/77, 1/11, 21/2, 5/7.$$
Beginnend mit einer ganzen Zahl $x$führen wir die folgende Operation aus: Multiplizieren Sie bei jedem Schritt $x$ durch den ersten Bruch (von links nach rechts) in der obigen Liste, der ein ganzzahliges Ergebnis ergibt.
Wenn die Liste keinen solchen Bruch enthält, endet die Prozedur und der Wert von $x$ ist das Endergebnis.
Beispiel: beginnend mit $x = 2$
Der erste Schritt: Multiplizieren Sie es mit $21/2$, was gibt $21$.
der zweite Schritt: multiplizieren Sie es mit $5/7$, was gibt $15$.
der dritte Schritt: multiplizieren Sie es mit $11/5$, was gibt $33$.
der vierte Schritt: multiplizieren Sie es mit $1/11$, was gibt $3$.
Wir sehen das $x = 3$ ist das Endergebnis als Multiplikation $3$ durch eine der fünf Brüche würde ein nicht ganzzahliges Ergebnis erhalten.
Frage: wenn wir anfangen mit $x = 2^{1234567}$Was sind dann die letzten drei Ziffern des Endergebnisses?
Anmerkung:
Dies ist bis zu einem gewissen Grad bekannt, und ich erwähne den Namen absichtlich nicht, da er so einfach sein sollte, dass kein zusätzliches Wissen erforderlich ist, um ihn zu lösen.
Natürlich können Sie gerne den Namen in Ihrer Antwort angeben!
Antworten
Wir beobachten das
Nur ein Bruch hat einen Nenner von 2
Da wir x = 2 ^ 1234567 haben, können wir versuchen, es anzuschließen. Wir werden die Primfaktorisierung der Zahlen verwenden, um die Dinge einfacher zu machen.
Wir multiplizieren zuerst mit 21/2 und erhalten 2 ^ 1234566 * 3 * 7. Da alle Brüche vor 21/2 einen anderen Primfaktor als 2, 3 oder 7 haben, wissen wir, dass die Funktion weiterhin mit 21/2 multipliziert wird bis es keine Faktoren von 2 mehr gibt. Dies lässt uns mit 3 ^ 1234567 * 7 ^ 1234567.
Nächster,
wir multiplizieren mit 5/7. Da der erste Bruch in der Liste einen Nenner von 5 hat, wissen wir, dass wir jedes Mal, wenn wir mit 5/7 multiplizieren, im Wesentlichen mit 11/7 multiplizieren. Wir multiplizieren und erhalten 3 ^ 1234567 * 7 ^ 1234566 * 11. 30/77 ist der nächste Bruch, mit dem multipliziert wird. Wir erhalten 2 * 3 ^ 1234568 * 5 * 7 ^ 1234565. Das Multiplizieren mit 11/5 ergibt 2 * 3 ^ 1234568 * 7 ^ 1234565 * 11.
Das merken wir
Weil wir so viele 7s haben, werden wir weiter mit 30/77 und 11/5 multiplizieren, bis uns die 7s ausgehen. Wir erkennen, dass jedes Mal, wenn die Anzahl der 7s um 1 abnimmt, die Anzahl der 2s um 1 und die Anzahl der 3s um 1 zunimmt. Wir erhöhen die Anzahl der Faktoren 2 und 3 um 1234565 und entfernen alle Faktoren von 7, um zu erhalten 2 ^ 1234566 * 3 ^ 2469133 * 11. Wir multiplizieren mit 1/11, um den Faktor 11 zu entfernen und 2 ^ 1234566 * 3 ^ 2469133 zu erhalten.
Dies lässt uns am selben Ort wie am Anfang, außer
Wir haben eine Reihe von Faktoren von 3 und die Anzahl von Faktoren von 2 hat sich um 1 verringert.
Da keiner der Nenner den Faktor 3 hat,
Wir werden das Gleiche tun wie zuvor, nur eine kleinere Anzahl von Malen. Das Eliminieren aller 2s ergibt 3 ^ 3703699 * 7 ^ 1234566. Wir multiplizieren mit 5/7 und dann mit 11/5, um 3 ^ 3703699 * 7 ^ 1234565 * 11 zu erhalten. Wir addieren die Potenzen von 2 und 3 zurück und entfernen alle Potenzen von 7 und die eine Potenz von 11, um 2 ^ 1234565 zu erhalten * 3 ^ 4938264.
Das merken wir
Beim ersten Mal erhöhte sich die Potenz von 3 um (1234567 + 1234566), und diesmal erhöhte sich die Potenz von 3 um (1234566 + 1234565). Dies bedeutet, dass bei einer Potenz von 2 die Potenz von 3 um (2x-1) erhöht wird. Dies bedeutet, dass die Potenz von 3 sein wird$\sum_{i=1}^{1234567} 2i-1$ Wir können Summationseigenschaften verwenden, um zu erhalten $2*\sum_{i=1}^{1234567} i - 1234567$. Wir wissen, dass die Summe der ersten$n$ positive ganze Zahlen ist $\frac{n*(n+1)}{2}$, so $\sum_{i=1}^{1234567} i = 1234567*1234568/2 = 762078456028$, so $2*\sum_{i=1}^{1234567} i - 1234567 = 1524155677489$
Wir sehen das
Die endgültige Antwort lautet 3 ^ 1524155677489, und da sich die letzten 3 Ziffern von 3 ^ x alle 100 Male wiederholen, müssen wir nur die Potenz von 3 (Mod 100) nehmen, was 89 ist.
Dies bedeutet, dass wir nur die letzten 3 Ziffern von finden müssen
3 ^ 89.
Wir wissen, dass die letzten 3 Ziffern von
3 ^ 10 sind 049,
was bedeutet, die letzten 3 Ziffern von
3 ^ 20 sind nur die letzten 3 Ziffern von 49 ^ 2 oder 401,
was bedeutet, die letzten 3 Ziffern von
3 ^ 40 sind nur die letzten 3 Ziffern von 401 ^ 2 oder 801,
was bedeutet, die letzten 3 Ziffern von
3 ^ 80 sind nur die letzten 3 Ziffern von 801 ^ 2 oder 601,
was bedeutet, die letzten 3 Ziffern von
3 ^ 89 sind nur die letzten 3 Ziffern von 601 * (die letzten 3 Ziffern von 3 ^ 9).
Wir wissen, dass die letzten 3 Ziffern von
3 ^ 9 sind nur 683, was bedeutet, dass die letzten 3 Ziffern von 3 ^ 89 die letzten 3 Ziffern von 601 * 683 sind, was 483 sind.
Dies bedeutet, dass unsere endgültige Antwort lautet
483.
Haftungsausschluss: Meine Berechnungen sind etwas chaotisch, und eine einzige Fehleinschätzung würde die gesamte Antwort falsch machen, aber die allgemeine Lösung sollte immer noch korrekt sein.
Ich möchte nicht snobistisch wirken, aber es ist wertvoll, etwas wirtschaftlich zu beweisen / zu berechnen. Machen wir also die zweite Hälfte (Berechnung der letzten drei Ziffern einer wahnsinnig hohen ganzzahligen Potenz) des Beweises richtig. Zuerst leiten wir ab$3^{100}\equiv 1 \mod 1000$ (ohne Euler zu benutzen $\phi$):
ab $3^5 = 243$ Nehmen wir die fünfte Potenz noch zweimal: Da wir nur die letzten drei Ziffern benötigen, ist dies mit dem Binomialsatz recht einfach, da leicht zu erkennen ist, dass der dritte und alle folgenden Terme durch 1000 teilbar sind und daher ignoriert werden können. $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$
Das ist also in beiden Fällen der gleiche Wert. Da 3 und 1000 relativ prim sind, schließen wir$3^{100} \equiv 1 \mod 1000$
Lassen Sie uns mit dieser Feststellung einen schmerzlosen Weg finden, um zu rechnen
$3^{89}$. Nach dem, was wir gerade gezeigt haben, haben wir$3^{89}\equiv \frac 1 {3^{11}} \mod 1000$. Nun ist es leicht zu erraten, dass die Umkehrung von$3$ Modulo $1000$ ist $-333$, das von $9$ ist $-111$. So:$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$