Recursive code exponentiation
I had a math question that was shown in olymipad somehwere and I am trying to implement it in code. The point is that I cannot understand the logic behind this problem.
Question:9 ^ (9 ^ (9 ^ (9 ^ ...... 1001 times ....))). What are the last 5 digits of the answer?
I would be glad if someone can tell me how to do this. Keep in mind that since I need to implement this in code, I benefit from a solution that takes fewer steps and is therefore more optimal in terms of complexity.
However, if you have any approach that comes up with the correct solution, I would like to know about this too, since I couldn't come up with this.
source to share
It looks like some of the other answers are calculating 9 ^ 1001. This is not a problem. It would be too easy for the Olympics problem.
We define T (a, n) so that T (a, 1) = a and T (a, n) = a ^ T (a, n-1). This is called tetration . The problem was given by T (91001) mod 100,000.
To make the issue as urgent, it is not clear which module to use. Not always T (a, n) mod m is T (a, n mod m) mod m. For example, T (2,3) = 2 ^ 2 ^ 2 = 2 ^ 4 = 16.T (2,4) = 2 ^ 16 = 65536. Mod 10, you can't just calculate T (2,3) mod 10 = 6 and then 2 ^ 6 mod 10 = 64 mod 10 = 4. The last digit of T (2,4) = 65536 is 6, not 4.
However, you might decide that 9 ^ 2500 = 1 mod 100000, so 9 ^ 100000 = 1 mod 100000. (By the Chinese remainder theorem, you can parse powers of 9 mod 2 ^ 5 and 5 ^ 5.) So you only need to keep track of the value T (9, n) mod 2500 or 100000 to determine T (9, 1001) mod 100000. Compute t = T (9.1000) mod 2500, and then compute powermod (9, t, 100000).
In fact, a function that maps n to 9 ^ n mod 100000 quickly settles to a fixed point at 45289.9 ^ 9 mod 2500 equals 489, 9 ^ 489 mod 2500 - 2289, 9 ^ 2289 mod 2500 - 289, and 9 ^ 289 mod 2500 is 289 again. Since 9 ^ 289 mod 100000 is 45289, T (9.4), T (9.5), ..., T (9.1001) all end in 45289.
Edit: Let me reiterate with Egor Skriptunov's comment. Powers 9 mod 10 ^ 5 cycle with period dividing phi (10 ^ 5) = 40,000, where phi is Euler's Totient function . So, we only need to determine T (9,1000) mod 40,000. The powers of the loop are 9 mod 40,000 with a period dividing phi (40000) = 16000, so we only need to find T (9999) mod 16000, etc. Since phi iterated 15 times by 10 ^ 5 is 1, we know the value of any degree 9 mod phi ^ 15 (10 ^ 5), and therefore T (9,16) = T (9, n) mod 10 ^ 5 for any larger p.
source to share