Quiero calcular últimos digts (tanto como sea posible ) de los siguientes números $$ N:=n^{n^{n^{\cdot^{\cdot^{\cdot^n}}}}}\!\!\!\hspace{5 mm}\mbox{ if there are $k$ many $n$'s in the expression and $n\in\mathbb{N}$ }$$ He visto muchos casos particulares de este problema. Creo que por extraño $n$ el dígito de las unidades es $n^3\mbox{ mod } 10 $ aún $n$ el dígito de las unidades es de 6, para todos los $k\geq 3$ . ¿Cuánto podemos decir acerca de los otros dígitos ?
Respuestas
¿Demasiados anuncios?
Shabaz
Puntos
403
Tomando $n=7$ y en busca de los tres últimos dígitos de un ejemplo, tenga en cuenta que $7^m \pmod {1000}$ es periódica con período de $20$. Esto se puede verificar fácilmente con una hoja de cálculo. Así que ahora, sólo necesitamos la torre por encima de la primera $7$$\pmod {20}$. Que tiene plazo,$4$, así que sólo necesitamos la torre por encima de los dos primeros a $7$'s $\pmod 4$. Que tiene plazo,$2$, y la pila por encima de la parte inferior tres $7$'s siempre es impar. Así que una torre de $k\ 7$'s de los últimos tres dígitos de la misma como $7^{7^7}$$ k \ge 4$. El superior de$7$$3 \pmod 4$, lo $7^7 \equiv 3 \pmod {20}$, lo $7^{7^7} \equiv 343 \pmod {1000}$, por lo que cualquier torre más alta termina en $343$
Tim Cochran
Puntos
804
Aquí un poco de conocimiento computacional...
Si queremos que la primera $d$ dígitos, se puede calcular el resultado de la aritmética modular. En otras palabras, modulo $10^d=2^d5^d$.
Los que consumen más tiempo de la porción es calcular el resultado modulo $5^m$. Podemos notar que $$k^m \mod n \equiv k^{m \mod \phi(n)} \mod n$$ where $\phi(n)$ es de Euler Totient función.
Podemos aplicar esta función de forma recursiva, es decir, $$m^m \mod n \equiv m^{m \mod \phi(n)} \mod n$$ $$m^{m^m} \mod n \equiv m^{\left(m^m \mod \phi(\phi(n))\right) \mod \phi(n)} \mod n$$ $$\dots$$ donde $n=5^d$. Por lo tanto, la más extensa operación de exponenciación modular $n$. Esto se puede hacer en $O(\log(n))$ operaciones a través de la exponenciación al cuadrado o exponenciación binaria. Esta operación se realiza en la mayoría de las $n$ veces, por lo que tenemos un conservador obligado de $O(n \log(n))$ o, realmente, $O(5^d \log(5^d))$ operaciones.
