Project Euler 832 - Mex Sequence

Official link:

Thought Process

As usual I tried to brute force the first few terms but I didn't find anything useful, however it did help me identify some very important patterns, below I list out the first 30 values.

Note for the rest of this explanation that ^ will denote the XOR operation,** will denote the power operation, and % will denote the modulus operation

Now clearly this problem has to do with powers of 4, so I tried taking a % 4, b % 4, c % 4 and I found the following pattern.

Investigating this pattern further we see that 

Using this observation we can use recursion to solve the problem. Since for every power of 4 block, it can be reduced into smaller power of 4 blocks with a different fixed sum

Lets say we want to find M(10)

We already know the a values, they will be (1, 4, 5, 6, 7, 16, 17, 18, 19, 20)

This can be a bit confusing to decipher, have a look at the code below (I have added some comments) to help you understand it!

Interactive Code

Input an integer (yourinput)

Code will output M(yourinput) (mod 1,000,000,007)