Project Euler 721 - High Powers of Irrational Numbers

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

Note: My code takes ~125 sec to run, but I'm happy with my solution

Thought Process

This problem was a bit of a combination of problems 318 and 752, I recommend you try those first before reading further or use them as a hint!

Using Problem 318, we can simplify the goal greatly, and by keeping everything as integers it's much easie to work with. Then using the same method as Problem 752 we just Exponentiation by Squaring find the desired x

In order to cut the run time down for this problem, I had a deeper look into exponentiation by squaring and ended up adding a few new functions to my python library mathslib and built a general function for this time of equations (seeing as I've already had to make it twice). I recommend reading this to learn how to efficiently implement this algorithm.

Interactive Code

Input an integer (yourinput)

Code will output G(yourinput) (mod 999,999,937)