Un puzzle de fraction
Il s'agit d'un puzzle avec à la fois l' étiquette de puzzle d' ordinateur et l'étiquette sans ordinateur .
Nous avons la liste suivante de cinq fractions:
$$11/5, 30/77, 1/11, 21/2, 5/7.$$
Commençant par un entier $x$, nous effectuons l'opération suivante: à chaque étape, multipliez $x$ par la première fraction (de gauche à droite) dans la liste ci-dessus qui donne un résultat entier.
S'il n'y a pas de telle fraction dans la liste, la procédure se termine et la valeur de $x$ est le résultat final.
Exemple: en commençant par $x = 2$
la première étape: multipliez-le par $21/2$, qui donne $21$.
la deuxième étape: multipliez-la par $5/7$, qui donne $15$.
la troisième étape: multipliez-la par $11/5$, qui donne $33$.
la quatrième étape: multipliez-la par $1/11$, qui donne $3$.
On voit ça $x = 3$ est le résultat final, en multipliant $3$ par l'une des cinq fractions donnerait un résultat non entier.
Question: si on commence par $x = 2^{1234567}$, alors quels seront les trois derniers chiffres du résultat final?
Remarque:
C'est dans une certaine mesure bien connu, et je ne mentionne pas intentionnellement le nom, car il devrait être suffisamment simple pour qu'aucune connaissance supplémentaire ne soit nécessaire pour le résoudre.
Bien sûr, vous êtes invités à indiquer le nom dans votre réponse!
Réponses
Nous observons que
une seule fraction a un dénominateur de 2
Comme nous avons x = 2 ^ 1234567, nous pouvons essayer de le brancher. Nous utiliserons la factorisation des nombres premiers pour faciliter les choses.
Nous multiplions d'abord par 21/2, obtenant 2 ^ 1234566 * 3 * 7. Comme toutes les fractions avant 21/2 ont un facteur premier autre que 2, 3 ou 7, nous savons que la fonction continuera à se multiplier par 21/2 jusqu'à ce qu'il ne reste plus de facteurs de 2. Cela nous laisse avec 3 ^ 1234567 * 7 ^ 1234567.
Suivant,
nous multiplions par 5/7. Parce que la première fraction de la liste a un dénominateur de 5, nous savons que chaque fois que nous multiplierons par 5/7, nous multiplierons essentiellement par 11/7. Nous multiplions et obtenons 3 ^ 1234567 * 7 ^ 1234566 * 11. 30/77 est la prochaine fraction par laquelle multiplier. Nous nous retrouvons avec 2 * 3 ^ 1234568 * 5 * 7 ^ 1234565. Multiplier par 11/5 nous donne 2 * 3 ^ 1234568 * 7 ^ 1234565 * 11.
Nous remarquons que
parce que nous avons un si grand nombre de 7, nous continuerons à multiplier par 30/77 et 11/5 jusqu'à ce que nous manquions de 7. On se rend compte que chaque fois que le nombre de 7 diminue de 1, le nombre de 2 augmente de 1 et le nombre de 3 augmente de 1. Nous augmentons le nombre de facteurs de 2 et 3 de 1234565 et supprimons tous les facteurs de 7 pour obtenir 2 ^ 1234566 * 3 ^ 2469133 * 11. Nous multiplions par 1/11 pour supprimer le facteur 11 et obtenir 2 ^ 1234566 * 3 ^ 2469133.
Cela nous laisse au même endroit que le début, sauf
nous avons un tas de facteurs de 3 et le nombre de facteurs de 2 a diminué de 1.
Parce qu'aucun des dénominateurs n'a un facteur de 3,
nous ferons la même chose qu'avant, juste un plus petit nombre de fois. L'élimination de tous les 2 nous donne 3 ^ 3703699 * 7 ^ 1234566. Nous multiplions par 5/7 puis 11/5 pour obtenir 3 ^ 3703699 * 7 ^ 1234565 * 11. Nous rajoutons les puissances de 2 et 3 et supprimons toutes les puissances de 7 et la puissance unique de 11 pour obtenir 2 ^ 1234565 * 3 ^ 4938264.
Nous remarquons que
la première fois, la puissance de 3 a augmenté de (1234567 + 1234566), et cette fois la puissance de 3 a augmenté de (1234566 + 1234565). Cela signifie que pour une puissance de 2, elle augmentera la puissance de 3 de (2x-1). Cela signifie que la puissance de 3 sera$\sum_{i=1}^{1234567} 2i-1$ Nous pouvons utiliser les propriétés de sommation pour obtenir $2*\sum_{i=1}^{1234567} i - 1234567$. Nous savons que la somme du premier$n$ les entiers positifs sont $\frac{n*(n+1)}{2}$, donc $\sum_{i=1}^{1234567} i = 1234567*1234568/2 = 762078456028$, donc $2*\sum_{i=1}^{1234567} i - 1234567 = 1524155677489$
On voit ça
la réponse finale est 3 ^ 1524155677489, et comme les 3 derniers chiffres de 3 ^ x se répètent toutes les 100 fois, nous devons seulement prendre la puissance de 3 (mod 100), qui est 89.
Cela signifie que nous avons juste besoin de trouver les 3 derniers chiffres de
3 ^ 89.
Nous savons que les 3 derniers chiffres de
3 ^ 10 sont 049,
ce qui signifie les 3 derniers chiffres de
3 ^ 20 ne sont que les 3 derniers chiffres de 49 ^ 2 ou 401,
ce qui signifie les 3 derniers chiffres de
3 ^ 40 ne sont que les 3 derniers chiffres de 401 ^ 2 ou 801,
ce qui signifie les 3 derniers chiffres de
3 ^ 80 ne sont que les 3 derniers chiffres de 801 ^ 2 ou 601,
ce qui signifie les 3 derniers chiffres de
3 ^ 89 ne sont que les 3 derniers chiffres de 601 * (les 3 derniers chiffres de 3 ^ 9).
Nous savons que les 3 derniers chiffres de
3 ^ 9 ne sont que 683, ce qui signifie que les 3 derniers chiffres de 3 ^ 89 sont les 3 derniers chiffres de 601 * 683, soit 483.
Cela signifie que notre réponse finale est
483.
Avertissement: Mes calculs sont un peu compliqués, et une seule erreur de calcul rendrait toute la réponse fausse, mais la solution générale devrait toujours être correcte.
Je ne veux pas paraître snob mais il y a de la valeur à prouver / calculer quelque chose économiquement. Faisons donc la seconde moitié (calculons les trois derniers chiffres d'une puissance entière incroyablement élevée) de la preuve correctement. Premièrement, nous dérivons$3^{100}\equiv 1 \mod 1000$ (sans utiliser Euler $\phi$):
a partir de $3^5 = 243$ prenons la cinquième puissance deux fois de plus: Puisque nous n'avons besoin que des trois derniers chiffres, c'est assez simple en utilisant le théorème binomial car on voit facilement que le troisième et tous les termes suivants sont divisibles par 1000 et peuvent donc être ignorés. $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$
C'est donc la même valeur dans les deux cas. Comme 3 et 1000 sont relativement premiers, nous concluons$3^{100} \equiv 1 \mod 1000$
Avec cela établi, trouvons un moyen de calcul indolore
$3^{89}$. Par ce que nous venons de montrer, nous avons$3^{89}\equiv \frac 1 {3^{11}} \mod 1000$. Maintenant, il est facile de deviner que l'inverse de$3$ modulo $1000$ est $-333$, celle de $9$ est $-111$. Donc:$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$