Berechnen Sie mit zwei Zahlen n und m den unendlichen Machtturm:

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

Denken Sie daran, dass ^ rechtsassoziativ ist. Also 2 ^ 3 ^ 4 = 2 ^ (3 ^ 4). Wie kann man nun einer unendlichen Folge von rechtsassoziativen Operatoren einen Wert zuweisen?

Definiere f (n, m, i) als den Kraftturm, der die ersten i Terme des unendlichen Kraftturms enthält. Dann gibt es eine solche Konstante C, dass für jedes i> C f (n, m, i) = f (n, m, C) ist. Man könnte also sagen, dass der unendliche Kraftturm sich einem bestimmten Wert annähert. Dieser Wert interessiert uns.

Ihr Programm muss in der Lage sein, n = 2017, m = 10 ^ 10 in weniger als 10 Sekunden auf einem vernünftigen modernen PC zu berechnen. Das heißt, Sie sollten einen tatsächlichen Algorithmus implementieren, kein Bruteforcing.

Sie können annehmen, dass n <2 ³⁰ und m <2 ⁵⁰ für die numerischen Grenzen in Ihrer Programmiersprache sind, aber Ihr Algorithmus muss theoretisch für jede Größe von n , m funktionieren . Ihr Programm muss jedoch für Eingaben innerhalb dieser Größengrenzen korrekt sein. Zwischenwertüberläufe werden nicht entschuldigt, wenn die Eingaben innerhalb dieser Grenzen liegen.

Beispiele:

2, 10^15
566088170340352

4, 3^20
4

32, 524287
16

Pyth, 23 Bytes

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

Definiert eine Funktion g, wobei m und n in dieser Reihenfolge verwendet werden.

Probieren Sie es online aus

Wie es funktioniert

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)

Probieren Sie es online!

Warum es funktioniert

Wir verwenden die folgende Verallgemeinerung des Satzes von Euler .

Lemma. n ^{2φ ( m )} ≡ n ^{φ ( m )} (mod m ) für alle n (ob oder ob nicht n ist coprime bis m ).

Beweis: Für alle Primkräfte p ^k dividiert m ,

• Wenn p n teilt , dann haben wir , weil φ ( m ) ≥ φ ( p ^k ) = p ^{k - 1} ( p - 1) ≥ 2 ^{k - 1} ≥ k , n 2 ^{φ ( m )} ≡ 0 ≡ n ^{φ ( m )} (mod p ^k ).
• Andernfalls , da φ ( p ^k ) dividieren φ ( m ), die Eulersche Satz gibt n ^{2φ ( m )} ≡ 1 ≡ n ^{φ ( m )} (mod p ^k ).

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

Logische Folge. Wenn k ≥ φ ( m ) ist, dann ist n ^k ≤ n ^{φ ( m ) + ( k mod φ ( m ))} (mod m ).

Beweis: Wenn k ≥ 2φ ( m ), das Lemma gibt n ^k = n ^{2φ ( m )} n ^{k - 2φ ( m )} ≡ n ^{φ ( m )} n ^{k - 2φ ( m )} = n ^{k - φ ( m )} ( mod m ) und wir wiederholen, bis der Exponent kleiner als 2φ ( m ) ist.

Haskell , 156 Bytes

(?)Nimmt zwei Integers und gibt ein Integer, use as zurück (10^10)?2017(umgekehrte Reihenfolge im Vergleich zu 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

Probieren Sie es online! (Diesmal habe ich die zu testenden Fälle in den Header eingefügt, da sie die Exponentiationsnotation verwenden.)

Seltsamerweise ist der langsamste Testfall nicht der mit einem Tempolimit (das ist fast augenblicklich), sondern der mit 524287 ? 32einer 524287viel größeren Primzahl als in den Faktoren der anderen Testfälle.

Wie es funktioniert

• (x&m)yist x^y `mod` m, oder Power Mod, die Potenzierung durch Quadrieren.
• n#pist die Euler-Totientenfunktion von n, vorausgesetzt es ngibt keine kleineren Primfaktoren als p.
  • mist nmit allen pFaktoren aufgeteilt.
  • Wenn es ksolche Faktoren gibt, sollte der Totient selbst einen entsprechenden Faktor erhalten (p-1)*p^(k-1), der berechnet wird als div(n*p-n)(p*m).
  • 1`max`...behandelt den Fall, wo neigentlich nicht teilbar war p, was das andere Argument maxgleich macht 0.
• Die Hauptfunktion m?nverwendet, dass, wenn ygroß genug n^y `mod` mist, dasselbe wie n^(t+(y`mod`t)) `mod` m, wenn tder Totient von ist m. (Die t+wird für diese Primfaktoren benötigt nund mhaben Gemeinsamkeiten, die alle maximiert werden.)
• Der Algorithmus stoppt, weil iterierte Totientenfunktionen schließlich 1 treffen.

Mathematica, 55 Bytes

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

Beispiele:

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

Probieren Sie es online!