Project Euler - Problem 18i

Official link: https://projecteuler.net/problem=18i

Note: You won't be able to access the link until you unlock the problem

Grade feel: 75% but requires Galois theory so perhaps harder!

Thought Process

One of my favourite ever problems! It requires Galois Theory to fully understand which is one of my favourite topics!

The problem was split into 2 parts for me. Part 1 I could do by myself, but Part 2 I needed help. I ended asking the question on Math StackExchange and got amazing help, in the end I used the idea to come with with my own slightly different solution (equivalent to the one shown) but this further solidifies my conviction for why this website is a good idea, since I was too inexperienced in Galois theory to think of this all by myself but now I have learnt a lot about how to work with finite fields and their extensions!

Following the last part, the implementation is now easy if you've practiced exponentiation before. I use my exponentiation algorithm which is a standard part of my library to find ρ for each prime depending on their value mod 12.

You could also use Tonelli-Shanks to find the square root of 3 in the p = 1 (mod 12) case but it turns out that the modular exponentiation was faster.

To generate the primes it took about 400 seconds using my own prime sieve, but using mCodings sieve I get the finally runtime to 55 seconds!

Interactive Code

Input an integer (yourinput)

Code will output the sum of R(p) for all primes p < yourinput