Evaluate modular power towers Given two numbers n and m, evaluate the infinite power tower:


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


Keep in mind that ^ is right-associative. So 2^3^4 = 2^(3^4). Now how can  you possibly assign a value to an infinite sequence of right-associative operators?

Define f(n,m,i) as the power tower containing the first i terms of the infinite power tower. Then there is some constant C such that for every i > C, f(n,m,i) = f(n,m,C). So you could say the infinite power tower converges on a certain value. We're interested in that value.



Your program must be able to compute n = 2017, m = 10^10 in under 10 seconds on a reasonable modern PC. That is, you should implement an actual algorithm, no bruteforcing.

You may assume that n &lt; 230 and m &lt; 250 for the numerical limits in your programming language, but your algorithm must theoretically work for any size n, m. However your program must be correct for inputs within these size limits, intermediate value overflows are not excused if the inputs are within these limits.

Examples:

2, 10^15
566088170340352

4, 3^20
4

32, 524287
16
Pyth, 23 bytes

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


Defines a function g, taking m and n in that order.

Try it online

How it works

M&amp;tG.^HsgBu-G/GH{PGGhHG
M                         def g(G, H):
 &amp;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)


Try it online!

Why it works

We use the following generalization of Euler’s theorem.

Lemma. n2φ(m) ≡ nφ(m) (mod m) for all n (whether or not n is coprime to m).

Proof: For all prime powers pk dividing m,


If p divides n, then because φ(m) ≥ φ(pk) = pk − 1(p − 1) ≥ 2k − 1 ≥ k, we have n2φ(m) ≡ 0 ≡ nφ(m) (mod pk).
Otherwise, because φ(pk) divides φ(m), Euler’s theorem gives n2φ(m) ≡ 1 ≡ nφ(m) (mod pk).


Therefore, n2φ(m) ≡ nφ(m) (mod m).

Corollary. If k ≥ φ(m), then nk ≡ nφ(m) + (k mod φ(m)) (mod m).

Proof: If k ≥ 2φ(m), the lemma gives nk = n2φ(m)nk - 2φ(m) ≡ nφ(m)nk - 2φ(m) = nk - φ(m) (mod m) and we repeat until the exponent is less than 2φ(m).