Hello coders,
Currently, I am stuck with the following problem: Given 2 powers, a[0] ^ (a[1] ^ (a[2] ^ (... ^ a[n]))) and b[0] ^ (b[1] ^ (b[2] ^ (... ^ b[m]))), how to compare these two powers? (a[i], b[i], n, m <= 100)
I believe that there must be some mathematical trick to solve this problem but I could not find out myself. I hope that someone can help me with this. Thank you very much.
Another matter is, I wonder if there is a simple and fast way to compute (a[0] ^ (a[1] ^ (a[2] ^ (... ^ a[n]))) % MOD) for some MOD. All I can think of is to use Euler theorem a ^ totient(MOD) = 1 (% MOD), but it seems pretty low. Can someone help me with this too?
Thank you for your time and consideration. Happy Coding
for the first one, you can compare it using logarithm, because a<b if and only if log(a)<log(b)
so we need to get the logarithm value and compare them example, N = 3 (remember log(a^b) = b*log(a) log(a[0] ^ (a[1] ^ (a[2)))) (a[1] ^ a[2]) * log(a[0])
log(a[1] ^ a[2] * log(a[0]))
log(a[1] ^ a[2]) + log(log(a[0]))
a[2] * log(a[1]) + log(log(a[0]))
Problem link?
This is Power Towers on Kattis, probably also hosted elsewhere. On Kattis, it's rated the most difficult problem, and it's for a reason. As far as reading comments of people who previously tried the problem, it seems that taking logarithms works for "most cases". However, the problem authors managed to come up with some nasty test cases, which apparently found a bug in Mathematica's power tower comparison algorithm. I believe that the general idea of taking logarithms is sound.
Some nasty test cases: 54^8^35^4 19^55^92^3
2^9^5^2 8^3^7^2
2^6^99^99^99^99 99^5^99^99^99^99
Which suggest we need to do some form of cases, since precision is not enough in some of them, and generalising too hastily could mess up the second case (which is totally equal).
As for modular arithmetic, taking totients is probably the right direction. So you might notice that the mod for powers repeats in a loop of totient of the power. (Eg. 3^x mod 7 is 3, 2, 6, 4, 5, 1, 3, 2, 6, ...) So it suffices to solve for x modulo 6, so 3^5^7, for example, will be the same as 3^5 modulo 7 (since 5^6 is 1 modulo 6). This can be done recursively, and takes at most O(log n) steps.
Thank you all.