13
2
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 < 230 and m < 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
Tip (for contenders):
n
andm
are not guaranteed to be co-prime. – Leaky Nun – 2017-06-03T16:28:12.697110^10 (and 10^20, and potentially 3^20 for signed integers) is larger than many languages' default integer types. Is it required that this large of an input be supported? – Doorknob – 2017-06-03T16:46:47.970
1@orlp Does that "yes" include 10^20? Because that doesn't fit in a 64-bit integer, so if you want to require it, I'd suggest pointing it out explicitly, because otherwise you're going to get a lot of invalid answers by people just assuming that 64 bit integers are going to be accurate enough. – Martin Ender – 2017-06-03T16:59:28.710
1Either way, what is the largest input we need to support? – Martin Ender – 2017-06-03T16:59:46.207
@Doorknob I added more lenient limits to the challenge. However your algorithm must theoretically work for any size m, n. – orlp – 2017-06-03T17:18:04.963