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
1,000
1.00Answer 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))