Étant donné deux nombres n et m, évaluez la tour de puissance infinie:

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

Gardez à l'esprit que ^ est associatif à droite. Donc 2 ^ 3 ^ 4 = 2 ^ (3 ^ 4). Maintenant, comment pouvez-vous éventuellement attribuer une valeur à une séquence infinie d'opérateurs associatifs à droite?

Définissez f (n, m, i) comme la tour de puissance contenant les i premiers termes de la tour de puissance infinie. Ensuite, il y a une constante C telle que pour chaque i> C, f (n, m, i) = f (n, m, C). On pourrait donc dire que la tour de puissance infinie converge vers une certaine valeur. Nous sommes intéressés par cette valeur.

Votre programme doit être capable de calculer n = 2017, m = 10 ^ 10 en moins de 10 secondes sur un PC moderne raisonnable. Autrement dit, vous devez implémenter un algorithme réel, pas de bruteforcing.

Vous pouvez supposer que n <2 ³⁰ et m <2 ⁵⁰ pour les limites numériques de votre langage de programmation, mais votre algorithme doit théoriquement fonctionner pour n'importe quelle taille n , m . Cependant, votre programme doit être correct pour les entrées dans ces limites de taille, les débordements de valeurs intermédiaires ne sont pas excusés si les entrées sont dans ces limites.

Exemples:

2, 10^15
566088170340352

4, 3^20
4

32, 524287
16

Pyth, 23 octets

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

Définit une fonction g, en prenant m et n dans cet ordre.

Essayez-le en ligne

Comment ça fonctionne

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 octets

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

Essayez-le en ligne!

Pourquoi ça marche

Nous utilisons la généralisation suivante du théorème d' Euler .

Lemme. n ^{2φ ( m )} ≡ n ^{φ ( m )} (mod m ) pour tous les n (si n est premier à m ).

Preuve: pour toutes les puissances premières p ^k divisant m ,

• Si p divise n , alors parce que φ ( m ) ≥ φ ( p ^k ) = p ^{k - 1} ( p - 1) ≥ 2 ^{k - 1} ≥ k , nous avons n ^{2φ ( m )} ≡ 0 ≡ n ^{φ ( m )} (mod p ^k ).
• Sinon, parce que φ ( p ^k ) divise φ ( m ), le théorème d'Euler donne n ^{2φ ( m )} ≡ 1 ≡ n ^{φ ( m )} (mod p ^k ).

Par conséquent, n ^{2φ ( m )} ≡ n ^{φ ( m )} (mod m ).

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

Preuve: Si k ≥ 2φ ( m ), le lemme donne n ^k = n ^{2φ ( m )} n ^{k - 2φ ( m )} ≡ n ^{φ ( m )} n ^{k - 2φ ( m )} = n ^{k - φ ( m )} ( mod m ) et nous répétons jusqu'à ce que l'exposant soit inférieur à 2φ ( m ).

Haskell , 156 octets

(?)prend deux Integers et retourne un Integer, utilisez as (10^10)?2017(ordre inversé par rapport à 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

Essayez-le en ligne! (J'ai mis les cas à tester dans l'en-tête cette fois, car ils utilisent la notation d'exponentiation.)

Curieusement, le cas de test le plus lent n'est pas celui avec une limite de vitesse (c'est presque instantané), mais l' 524287 ? 32un, car il 524287s'agit d'un nombre premier beaucoup plus grand que celui qui apparaît dans les facteurs des autres cas de test.

Comment ça fonctionne

• (x&m)yest x^y `mod` m, ou mod de puissance, utilisant l'exponentiation par quadrature.
• n#pest la fonction de totient d'Euler de n, en supposant qu'il nn'y a pas de facteurs premiers plus petits que p.
  • mest navec tous les pfacteurs divisés.
  • S'il existe de ktels facteurs, le totient doit lui-même obtenir un facteur correspondant (p-1)*p^(k-1), qui est calculé comme div(n*p-n)(p*m).
  • 1`max`...gère le cas où nn'était pas réellement divisible par p, ce qui rend l'autre argument maxégal à 0.
• La fonction principale m?nutilise que quand yest assez grand, n^y `mod` mest le même que n^(t+(y`mod`t)) `mod` m, quand test le totient de m. (Le t+est nécessaire pour ces facteurs premiers net mont en commun, qui sont tous maximisés.)
• L'algorithme s'arrête car les fonctions totientes itérées atteignent finalement 1.

Mathematica, 55 octets

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

Exemples:

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 octets

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

Essayez-le en ligne!