Voy a mostrar cómo, en general, para evaluar $a_1^{\,a_2^{\,\cdots}} \bmod m$, de forma recursiva.
Si $(a_1 \bmod m) \leq 1$,$a_1^{\,a_2^{\,\cdots}} \equiv a_1 \mod m$.
De lo contrario, si $\gcd(a_1, m) = 1$,$a_1^{\,a_2^{\,\cdots}} \equiv a_1^{\,a_2^{\,\cdots} \bmod \phi(m)}\mod m$. De forma recursiva evaluar $r = a_2^{\,a_3^{\,\cdots}} \bmod \phi(m)$, y, a continuación, calcular el $a_1^r \bmod m$.
-
De lo contrario, factorizar $m$ en números primos. Si $m$ es una fuente primaria de energía $p^k$, pero $\gcd(a_1, p^k) \neq 1$,$\gcd(a_1, p^k) = p^i$. Escribir $a'_1 = a_1/p^i$, luego tenemos a $a_1^{\,a_2^{\,\cdots}} \equiv a_1'^{\,a_2^{\,\cdots}}\cdot(p^i)^{\,a_2^{\,\cdots}} \mod p^k$.
Nos evaluar de forma recursiva $r \equiv a_1'^{\,a_2^{\,\cdots}} \equiv a_1'^{\,a_2^{\,\cdots}\bmod \phi(p^k)} \equiv a_1'^{\,a_2^{\,\cdots}\bmod p^k - p^{k-1}} \mod p^k$.
$s \equiv (p^i)^{\,a_2^{\,\cdots}} \equiv p^{i\,a_2^{\,\cdots}} \bmod p^k$ es diferente al resto. Si $i\,a_2^{\,a_3^{\,\cdots}} \geq k$$s = 0$, de lo contrario, simplemente tenemos que evaluar más grande y más grande prefijos de $a$. Si bien el poder de la torre se hace demasiado grande, o se llega a un $0$ o $1$, nos detenemos, evaluar el poder de la torre y encontrar $s$. Esto siempre es un proceso finito, la torre no va a ser más de $1 + \log_2k$ (esto es incluso una mala límite superior, el real es el tetra-logaritmo).
Entonces nos encontramos con la $st \bmod m$ y hemos terminado.
De forma recursiva evaluar $a_1^{\,a_2^{\,\cdots}} \bmod p^k$ por cada $p,k$ en la factorización de $m$. A continuación, utilice el teorema del resto Chino para encontrar $a_1^{\,a_2^{\,\cdots}} \bmod m$.
Tenga en cuenta que para cualquier secuencia $a$, y cualquier módulo de $m$, esto se termina, como en cada paso recursivo $m$ disminuye, y $m$ es finito. Incluso cuando $a$ es infinito.
Una implementación en Python usando sympy (con zero basado en la indexación de $a$):
from math import gcd, log
from sympy.ntheory import totient, factorint
from sympy.ntheory.modular import crt
def evaltowermax(l, k):
r = 1
for e in l[::-1]:
# Prevent evaluation of large powers, 0.1 to account for errors.
if log(e)*r - 0.1 > log(k):
r = k
break
r = e**r
return r
def modulartower(af, m, n=0):
a = af(n); g = gcd(a, m)
if a % m <= 1: return a % m
if g == 1: return pow(a, modulartower(af, totient(m), n + 1), m)
f = factorint(m)
if len(f) == 1: # Prime power.
p, i = factorint(g).popitem()
k = f[p]
tower = [af(ti) for ti in range(n, n + k.bit_length() + 1)]
s = pow(p, i * evaltowermax(tower, k), m)
if s == 0: return 0
aprimef = lambda l: a // p**i if l == n else af(l)
t = modulartower(aprimef, p**k - p**(k-1), n)
return s*t % m
m = [p**k for p, k in f.items()]
r = [modulartower(af, p**k, n) for p, k in f.items()]
return crt(m, r)[0]
print(modulartower(lambda n: 2017 + n, 10**20))
Este calcula los últimos 20 dígitos de $2017^{2018^{\cdots}}$ en un instante como $77345043177395978241$.
Simplificado el algoritmo debido a usuario Feersum:
Si $(a_1 \bmod m) \leq 1$,$a_1^{\,a_2^{\,\cdots}} \equiv a_1 \mod m$.
-
De lo contrario, el factor de $m$ en números primos $p_i$. Calculamos $\displaystyle x = \prod_{\gcd(p_i, a) = 1} p_i$$y = m/x$.
A continuación, calculamos el $a_1^{\,a_2^{\,\cdots}}\bmod x$ $a_1^{\,a_2^{\,\cdots}}\bmod y$ y utilizar el teorema del resto Chino para encontrar $a_1^{\,a_2^{\,\cdots}}\bmod xy = a_1^{\,a_2^{\,\cdots}}\bmod m$.
Desde $a_1$ $x$ son coprime tenemos $a_1^{\,a_2^{\,\cdots}}\equiv a_1^{\,a_2^{\,\cdots} \bmod \phi(x)} \mod x$. Podemos calcular recursivamente $r = a_2^{\,a_3^{\,\cdots}} \bmod \phi(x)$ y, a continuación, calcular $a_1^r \mod x$ directamente.
$a_1$ $y$ es un poco interesante, como $y$ sólo se compone de números primos que se encuentran en la descomposición de la $a_1$. Así, por una lo suficientemente grande como $k$ tenemos $a_1^k \equiv 0 \mod y$. Para una secuencia infinita $a$ sin $0$ o $1$ elementos, este es siempre el caso. Si una secuencia infinita contiene $0$ o $1$ elementos o la secuencia es finito, debemos evaluar la primer torre de $a_1^{\,a_2^{\,\cdots}}\bmod y$, por suerte sólo necesitamos evaluar $\log_2 y + 1$ pasos en el peor.
