Project Euler 717 - Summation of a Modular Formula
Official link: https://projecteuler.net/problem=717
Modulo calculations can always be a bit tricky, too me a while to fully understand the maths behind this problem, but the first thing to realize is that implementation of f(p), g(p) are very easy.
The problem is really about avoiding the explicit calculations of 2^p, 2^(2^p), etc and making use of the modulus to give the answer easily.
I did the following first:
You can see that we have found an easy way to calculate r, p^(-1), and even removed the need to take the modulus at the end, this makes it much easier to calculate as we can use the pow function in python. However, we are left with the 2^(p-1) still, but we will simplify this with the help of the mod(p) from g(p).
Enter an integer (yourinput)
Code will output G(yourinput)