Um quebra-cabeça de fração
Este é um quebra-cabeça com a tag computer-puzzle e a tag no-computers .
Temos a seguinte lista de cinco frações:
$$11/5, 30/77, 1/11, 21/2, 5/7.$$
Começando com um inteiro $x$, realizamos a seguinte operação: em cada etapa, multiplicar $x$ pela primeira fração (da esquerda para a direita) na lista acima que fornece um resultado inteiro.
Se não houver tal fração na lista, o procedimento termina e o valor de $x$ é o resultado final.
Exemplo: começando com $x = 2$
o primeiro passo: multiplique por $21/2$, que dá $21$.
a segunda etapa: multiplique por $5/7$, que dá $15$.
a terceira etapa: multiplique por $11/5$, que dá $33$.
a quarta etapa: multiplique por $1/11$, que dá $3$.
Nós vemos que $x = 3$ é o resultado final, multiplicando $3$ por qualquer uma das cinco frações daria um resultado não inteiro.
Pergunta: se começarmos com $x = 2^{1234567}$, então quais serão os últimos três dígitos do resultado final?
Observação:
Isso é até certo ponto bem conhecido, e intencionalmente não menciono o nome, pois deve ser simples o suficiente para que nenhum conhecimento extra seja necessário para resolvê-lo.
Claro, você pode apontar o nome em sua resposta!
Respostas
Nós observamos que
apenas uma fração tem um denominador de 2
Como temos x = 2 ^ 1234567, podemos tentar ligá-lo. Usaremos a fatoração primária dos números para tornar as coisas mais fáceis.
Primeiro multiplicamos por 21/2, obtendo 2 ^ 1234566 * 3 * 7. Como todas as frações antes de 21/2 têm um fator primo diferente de 2, 3 ou 7, sabemos que a função continuará se multiplicando por 21/2 até que não haja fatores de 2 restantes. Isso nos deixa com 3 ^ 1234567 * 7 ^ 1234567.
Próximo,
nós multiplicamos por 5/7. Como a primeira fração da lista tem um denominador 5, sabemos que sempre que multiplicarmos por 5/7, estaremos essencialmente multiplicando por 11/7. Multiplicamos e obtemos 3 ^ 1234567 * 7 ^ 1234566 * 11. 30/77 é a próxima fração pela qual multiplicar. Acabamos com 2 * 3 ^ 1234568 * 5 * 7 ^ 1234565. Multiplicando por 11/5 resulta 2 * 3 ^ 1234568 * 7 ^ 1234565 * 11.
Nós notamos que
como temos uma grande quantidade de 7s, continuaremos multiplicando por 30/77 e 11/5 até esgotar os 7s. Percebemos que cada vez que o número de 7s diminui em 1, o número de 2s aumenta em 1 e o número de 3s aumenta em 1. Aumentamos o número de fatores de 2 e 3 em 1234565 e removemos todos os fatores de 7 para obter 2 ^ 1234566 * 3 ^ 2469133 * 11. Multiplicamos por 1/11 para remover o fator 11 e obtemos 2 ^ 1234566 * 3 ^ 2469133.
Isso nos deixa no mesmo lugar do início, exceto
temos um monte de fatores de 3 e o número de fatores de 2 diminuiu em 1.
Porque nenhum dos denominadores tem um fator de 3,
faremos a mesma coisa de antes, apenas um número menor de vezes. Eliminar todos os 2s resulta em 3 ^ 3703699 * 7 ^ 1234566. Multiplicamos por 5/7 e depois 11/5 para obter 3 ^ 3703699 * 7 ^ 1234565 * 11. Adicionamos de volta as potências de 2 e 3 e removemos todas as potências de 7 e uma potência de 11 para obter 2 ^ 1234565 * 3 ^ 4938264.
Nós notamos que
na primeira vez, a potência de 3 aumentou em (1234567 + 1234566) e, desta vez, a potência de 3 aumentou em (1234566 + 1234565). Isso significa que para uma potência de 2, aumentará a potência de 3 em (2x-1). Isso significa que a potência de 3 será$\sum_{i=1}^{1234567} 2i-1$ Podemos usar propriedades de soma para obter $2*\sum_{i=1}^{1234567} i - 1234567$. Sabemos que a soma do primeiro$n$ inteiros positivos são $\frac{n*(n+1)}{2}$, assim $\sum_{i=1}^{1234567} i = 1234567*1234568/2 = 762078456028$, assim $2*\sum_{i=1}^{1234567} i - 1234567 = 1524155677489$
Nós vemos que
a resposta final é 3 ^ 1524155677489 e, como os últimos 3 dígitos de 3 ^ x se repetem a cada 100 vezes, precisamos apenas obter a potência de 3 (mod 100), que é 89.
Isso significa que só precisamos encontrar os últimos 3 dígitos de
3 ^ 89.
Sabemos que os últimos 3 dígitos de
3 ^ 10 são 049,
o que significa os últimos 3 dígitos de
3 ^ 20 são apenas os últimos 3 dígitos de 49 ^ 2 ou 401,
o que significa os últimos 3 dígitos de
3 ^ 40 são apenas os últimos 3 dígitos de 401 ^ 2 ou 801,
o que significa os últimos 3 dígitos de
3 ^ 80 são apenas os últimos 3 dígitos de 801 ^ 2 ou 601,
o que significa os últimos 3 dígitos de
3 ^ 89 são apenas os últimos 3 dígitos de 601 * (os últimos 3 dígitos de 3 ^ 9).
Sabemos que os últimos 3 dígitos de
3 ^ 9 são apenas 683, o que significa que os últimos 3 dígitos de 3 ^ 89 são os últimos 3 dígitos de 601 * 683, que são 483.
Isso significa que nossa resposta final é
483.
Isenção de responsabilidade: meus cálculos são um pouco confusos e um único erro de cálculo tornaria toda a resposta errada, mas a solução geral ainda deve estar correta.
Não quero parecer esnobe, mas vale a pena provar / calcular algo economicamente. Então, vamos fazer a segunda metade (computando os últimos três dígitos de uma potência inteira insanamente alta) da prova corretamente. Primeiro, nós derivamos$3^{100}\equiv 1 \mod 1000$ (sem usar Euler $\phi$):
Começando de $3^5 = 243$ vamos pegar a quinta potência mais duas vezes: Como precisamos apenas dos três últimos dígitos, isso é bastante simples usando o teorema binomial porque é facilmente visto que o terceiro e todos os termos seguintes são divisíveis por 1000 e, portanto, podem ser ignorados. $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$
Portanto, esse é o mesmo valor em ambos os casos. Como 3 e 1000 são relativamente primos, concluímos$3^{100} \equiv 1 \mod 1000$
Com isso estabelecido, vamos encontrar uma maneira indolor de computação
$3^{89}$. Pelo que acabamos de mostrar, temos$3^{89}\equiv \frac 1 {3^{11}} \mod 1000$. Agora, é fácil adivinhar que o inverso de$3$ modulo $1000$ é $-333$, que de $9$ é $-111$. Portanto:$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$