Dados dos números n y m, evalúe la torre de energía infinita:

n ^ (n + 1) ^ (n + 2) ^ (n + 3) ^ (n + 4) ^ ... mod m

Tenga en cuenta que ^ es asociativo correcto. Entonces 2 ^ 3 ^ 4 = 2 ^ (3 ^ 4). Ahora, ¿cómo puede asignar un valor a una secuencia infinita de operadores asociativos a la derecha?

Defina f (n, m, i) como la torre de energía que contiene los primeros términos i de la torre de energía infinita. Entonces hay una constante C tal que para cada i> C, f (n, m, i) = f (n, m, C). Entonces se podría decir que la torre de energía infinita converge en un cierto valor. Estamos interesados ​​en ese valor.

Su programa debe poder calcular n = 2017, m = 10 ^ 10 en menos de 10 segundos en una PC moderna razonable. Es decir, debe implementar un algoritmo real, sin fuerza bruta.

Es posible suponer que n <2 ³⁰ y m <2 ⁵⁰ para los límites numéricos en su lenguaje de programación, pero su algoritmo debe teóricamente trabajo para cualquier tamaño n , m . Sin embargo, su programa debe ser correcto para las entradas dentro de estos límites de tamaño, los desbordamientos de valores intermedios no están justificados si las entradas están dentro de estos límites.

Ejemplos:

2, 10^15
566088170340352

4, 3^20
4

32, 524287
16

Pyth, 23 bytes

M&tG.^HsgBu-G/GH{PGGhHG

Define una función g, teniendo m y n en ese orden.

Pruébalo en línea

Cómo funciona

M&tG.^HsgBu-G/GH{PGGhHG
M                         def g(G, H):
 &tG                        0 if G == 1, else …
                 PG         prime factors of G
                {           deduplicate that
          u-G/GH   G        reduce that on lambda G,H:G-G/H, starting at G
                              (this gives the Euler totient φ(G))
        gB          hH      bifurcate: two-element list [that, g(that, H + 1)]
       s                    sum
    .^H               G     H^that mod G

Python 2, 109 76 bytes

import sympy
def g(n,m):j=sympy.totient(m);return m-1and pow(n,j+g(n+1,j),m)

Pruébalo en línea!

Por que funciona

Utilizamos la siguiente generalización del teorema de Euler .

Lema n ^{2φ ( m )} ≡ n ^{φ ( m )} (mod m ) para todos los n (independientemente de si n es coprime para m ).

Prueba: para todas las potencias primarias p ^k dividiendo m ,

• Si p divide n , entonces porque φ ( m ) ≥ φ ( p ^k ) = p ^{k - 1} ( p - 1) ≥ 2 ^{k - 1} ≥ k , tenemos n ^{2φ ( m )} ≡ 0 ≡ n ^{φ ( m )} (mod p ^k ).
• De lo contrario, debido a que φ ( p ^k ) divide a φ ( m ), el teorema de Euler da n ^{2φ ( m )} ≡ 1 ≡ n ^{φ ( m )} (mod p ^k ).

Por lo tanto, n ^{2φ ( m )} ≡ n ^{φ ( m )} (mod m ).

Corolario. Si k ≥ φ ( m ), entonces n ^k ≡ n ^{φ ( m ) + ( k mod φ ( m ))} (mod m ).

Prueba: si k ≥ 2φ ( m ), el lema da n ^k = n ^{2φ ( m )} n ^{k - 2φ ( m )} ≡ n ^{φ ( m )} n ^{k - 2φ ( m )} = n ^{k - φ ( m )} ( mod m ) y repetimos hasta que el exponente sea menor que 2φ ( m ).

Haskell , 156 bytes

(?)toma dos Integersy devuelve un Integer, usar como (10^10)?2017(orden inverso en comparación con OP).

1?n=0
m?n=n&m$m#2+m#2?(n+1)
1#_=1
n#p|m<-until((<2).gcd p)(`div`p)n=m#(p+1)*1`max`div(n*p-n)(p*m)
(_&_)0=1
(x&m)y|(a,b)<-divMod y 2=mod(x^b*(mod(x*x)m&m)a)m

Pruébalo en línea! (Esta vez pongo los casos a prueba en el encabezado, ya que usan la notación de exponenciación).

Curiosamente, el caso de prueba más lento no es el que tiene un límite de velocidad (que es casi instantáneo), sino el 524287 ? 32uno, porque 524287es un primo mucho mayor que el que aparece en los factores de los otros casos de prueba.

Cómo funciona

• (x&m)yes x^y `mod` m, o mod de potencia, usando exponenciación al cuadrado.
• n#pes la función totient de Euler n, suponiendo que nno tenga factores primos más pequeños que p.
  • mEs ncon todos los pfactores divididos.
  • Si existen ktales factores, el cliente mismo debería obtener un factor correspondiente (p-1)*p^(k-1), que se calcula como div(n*p-n)(p*m).
  • 1`max`...maneja el caso donde en nrealidad no era divisible por p, lo que hace que el otro argumento sea maxigual a 0.
• La función principal m?nutiliza que cuando yes lo suficientemente grande, n^y `mod` mes lo mismo que n^(t+(y`mod`t)) `mod` m, cuando tes el total de m. ( t+Es necesario para esos factores primos ny mtienen en común, que todos se maximizan).
• El algoritmo se detiene porque las funciones iterativas totient eventualmente llegan a 1.

Mathematica, 55 bytes

n_~f~1=0;n_~f~m_:=PowerMod[n,(t=EulerPhi@m)+f[n+1,t],m]

Ejemplos:

In[1]:= n_~f~1=0;n_~f~m_:=PowerMod[n,(t=EulerPhi@m)+f[n+1,t],m]

In[2]:= f[2, 10^15]

Out[2]= 566088170340352

In[3]:= f[4, 3^20]

Out[3]= 4

In[4]:= f[32, 524287]

Out[4]= 16

In[5]:= f[2017, 10^10]

Out[5]= 7395978241

Pari / GP , 59 bytes

f(n,m)=if(m==1,0,lift(Mod(n,m)^((t=eulerphi(m))+f(n+1,t))))

Pruébalo en línea!