Dados dois números n e m, avalie a torre de poder infinita:

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

Lembre-se de que ^ é associativo correto. Então 2 ^ 3 ^ 4 = 2 ^ (3 ^ 4). Agora, como você pode atribuir um valor a uma sequência infinita de operadores associativos à direita?

Defina f (n, m, i) como a torre de força que contém os primeiros termos i da torre de força infinita. Então existe uma constante C tal que, para todo i> C, f (n, m, i) = f (n, m, C). Então, você poderia dizer que a torre de energia infinita converge para um determinado valor. Estamos interessados ​​nesse valor.

Seu programa deve poder calcular n = 2017, m = 10 ^ 10 em menos de 10 segundos em um PC moderno razoável. Ou seja, você deve implementar um algoritmo real, sem força bruta.

Você pode assumir que n <2 ³⁰ e m <2 ⁵⁰ para os limites numéricos em sua linguagem de programação, mas seu algoritmo deve teoricamente funcionar para qualquer tamanho n , m . No entanto, seu programa deve estar correto para entradas dentro desses limites de tamanho, excedentes de valores intermediários não serão desculpados se as entradas estiverem dentro desses limites.

Exemplos:

2, 10^15
566088170340352

4, 3^20
4

32, 524287
16

Pitão, 23 bytes

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

Define uma função g, tomando m e n nessa ordem.

Experimente online

Como 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)

Experimente online!

Por que funciona

Usamos a seguinte generalização do teorema de Euler .

Lema. n ^{2φ ( m )} ≡ n ^{φ ( m )} (mod m ) para todos os n (independentemente de n ser coprime para m ).

Prova: Para todas as potências primárias p ^k dividindo m ,

• Se p divide n , então porque φ ( m ) ≥ φ ( p ^k ) = p ^{k - 1} ( p - 1) ≥ 2 ^{k - 1} ≥ k , temos n ^{2φ ( m )} ≡ 0 ≡ n ^{φ ( m )} (mod p ^k ).
• Caso contrário, como φ ( p ^k ) divide φ ( m ), o teorema de Euler fornece n ^{2φ ( m )} ≡ 1 ≡ n ^{φ ( m )} (mod p ^k ).

Portanto, n ^{2φ ( m )} ≡ n ^{φ ( m )} (mod m ).

Corolário. Se k ≥ φ ( m ), então n ^k ≡ n ^{φ ( m ) + ( k mod φ ( m) ))} (mod m ).

Prova: Se k ≥ 2φ ( m ), o lema fornece n ^k = n ^{2φ ( m )} n ^{k - 2φ ( m )} ≡ n ^{φ ( m )} n ^{k - 2φ ( m )} = n ^{k - φ ( m )} ( mod m ) e repetimos até que o expoente seja menor que 2φ ( m ).

Haskell , 156 bytes

(?)leva dois se Integerretorna um Integer, use como (10^10)?2017(ordem inversa em comparação com 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

Experimente online! (Coloquei os casos para testar no cabeçalho dessa vez, pois eles usam notação de exponenciação.)

Curiosamente, o caso de teste mais lento não é aquele com limite de velocidade (quase instantâneo), mas o 524287 ? 32 primeiro, porque 524287é um primo muito maior do que aparece nos fatores dos outros casos de teste.

Como funciona

• (x&m)y é x^y `mod` m , ou mod de poder, usando exponenciação ao quadrado.
• n#pé a função totiente de Euler de n, assumindo nque não há fatores primos menores que p.
  • mestá ncom todos os pfatores divididos.
  • Se houver ktais fatores, o próprio paciente deve obter um fator correspondente (p-1)*p^(k-1), calculado como div(n*p-n)(p*m).
  • 1`max`...lida com o caso em que nnão era realmente divisível por p, o que torna o outro argumento maxigual a 0.
• A função principal m?nusa que quando yé grande o suficiente, n^y `mod` mé o mesmo que n^(t+(y`mod`t)) `mod` m, quando té o totiente de m. (O t+necessário para esses fatores primosnm Isso e tem em comum, que são maximizados.)
• O algoritmo para porque as funções iteradas de totient eventualmente atingem 1.

Mathematica, 55 bytes

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

Exemplos:

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))))

Experimente online!