Project Euler 717 - Summation of a Modular Formula

Official link: https://projecteuler.net/problem=717

Thought Process

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:

To calculate them we use Fermat's Little Theorem

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).

Interactive Code

Enter an integer (yourinput)

Code will output G(yourinput)