# Project Euler 752 - Powers of 1 + √7

Note: My code takes ~230 seconds. I have given details on why everything is true, I understand the more detailed explanations in the thread so I am happy with my understanding.

# Thought Process

I found this problem really hard. It took me a long time to figure out basic things about the problem, and I found most of them by pure brute force and was only able to prove them after taking the time to understand other peoples solutions.

Through complete brute force for G(1000) and using Binomial expansions (which is very slow) I noticed some very crucial compenents of the problem.

I could not prove these and even then my program was way too slow. After some inspiration from https://mathlesstraveled.com/2017/07/06/the-curious-powers-of-1-sqrt-2-recurrences/ I realised I had wasted a lot of time and not realised the obvious way to approach this problem.

With these expression I could calculate (1 + √(7))^n extremely quickly using binary exponentiation. With this, the problem is solvable

I struggled to find a smart way to deal with the constant need to find the divisors of p^2 - 1 in the end I just used sympy divisors function as it is much faster than mine and I could solve the problem.

Below I give some justification for the points 1-4 listed above:

For actual proof we need some group/field theory which I can personally understand but my explanations will not be as good as those in the thread, hence I recommend you read the thread for a proper understanding of what is going on.

# Interactive Code

Enter an integer (yourinput)

Code will output G(yourinput)