Project Euler 463 - A weird recurrence relation

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

Thought Process

Firstly it is clear that we must somehow find a formula for S as 3^37 is much too massive. Secondly the problem seems to be working with numbers mod 4, so I tried to incorporate that into my thinking.

The first thing I wanted to do is understand f, so we re-write it as such;

My next goal is to find a formula for S(4n + 3), I derive some identities with f(4n + 3), f(4n + 2), f(4n + 1), and f(4n).

Using 4 we can generate the required recurrence,

However a minor correction needs to be made,

And voila we now have a recurrence relation which is simple to implement, but it still takes a while so we need to cache the data, otherwise it will never finish running, luckily I have just learnt about python Decorators, specifically the cache decorator which I found from this video, essentially this is an inbuilt memoization function! It is extremely useful and I have been waiting for an opportunity to use this.

Interactive Code

Enter 2 integers (base, pow)

Code will output S(base^pow) % 10^9