What is 5000000 ^ (5000001 ^ (5000002 ^ (... 5000050))) modulo 4816745263172635244
No bounty left

this should be solved with a program of some sort of course

solution alone isn't enough, need to present at least some description of approach or code

Get
Ṁ1,000
and
S1.00
Sort by:
+Ṁ200

Answer is 98757822013699692. Here is a program which recursively reduces entries of a power tower by Euler's phi function of a modular divisor:

cap = int(1e9)

def factors(k):

if k < 4:

return [] if k == 1 else [k]

for i in range(2, min(cap, int(k**0.5) + 1)):

if k % i == 0:

while k % i == 0:

k //= i

return [i] + factors(k)

return [k] # prime


def phi(k):

total = k

for p in factors(k):

total -= total//p

return total

def manual(base, exp, mod):

total = 1

temp = base % mod

for i in bin(exp)[:1:-1]:

if i == '1':

total = (total * temp) % mod

temp = (temp * temp) % mod

return total

def power_mod(power_list, mod):

if len(power_list) == 1:

return power_list[0] % mod

return manual(power_list[0], power_mod(power_list[1:], phi(mod)), mod)

print(power_mod(list(range(5000000,5000051)), 4816745263172635244))