Project Euler 832 - Mex Sequence
Official link: https://projecteuler.net/problem=832
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.
If a = 0 % 4, then b = c = 0 % 4
If a = 1 % 4, then b = 2 % 4, c = 3 % 4
If a = 2 % 4, then b = 3 % 4, c = 1 % 4
If a = 3 % 4, then b = 1 % 4, c = 2 % 4
Investigating this pattern further we see that
If 4^i ≤ a < 4**i + 1*4**(i - 1)
Then 2*4**i ≤ b < 2*4**i + 4**(i - 1)
And 3*4**i ≤ c < 3*4**i + 4**(i - 1)
If 4**i + 4**(i - 1) ≤ a < 4**i + 2*4**(i - 1)
Then 2*4**i + 2*4**(i - 1) ≤ b < 2*4**i + 3*4**(i - 1)
And 3*4**i + 3*4**(i-1) ≤ c < 3*4**i + 4*4**(i - 1)
If 4**i + 2*4**(i - 1) ≤ a < 4**i + 3*4**(i - 1)
Then 2*4**i + 3*4**(i - 1) ≤ b < 2*4**i + 4*4**(i - 1)
And 3*4**i + 4**(i - 1) ≤ c < 3*4**i + 2*4**(i - 1)
If 4**i + 3*4**(i - 1) ≤ a < 4**i + 4*4**(i - 1)
Then 2*4**i + 4**(i - 1) ≤ b < 2*4**i + 1*4**(i - 1)
And 3*4**i + 2*4**(i - 1) ≤ c < 3*4**i + 3*4**(i - 1)
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)
When a = 1, with i = 0 we have case 1 above
Hence b = 2, c = 3
Total = 6
When a = 4, 5, 6, 7, with i = 1 we have case 1, 2, 3, 4 respectively
Hence b = 8, 10, 9, 11 and c = 12, 15, 13, 14 (Note that the order doesn't matter, we will just quickly sum the whole block since we know the start and the end of a, b, and c)
Total = 114
When a = 16, 17, 18, 19, with i = 2 we have case 1
Hence b = 32, 33, 34, 35, and c = 38, 39, 50, 51 (Note that the order is no longer necessarily correct)
Total = 402
When a = 20, with i = 2 we have case 2
Now it's more complicated since we can't tell what value b, c will have, however we know they will greater than or equal to 40 and 60 respectively
Now we reduce this block of 4 to a lower power, that is i = 1
Then we know we are in case 1 again, hence we know b = 0 + 40, and c = 0 + 60
Total = 120
Overall = 6 + 114 + 402 + 120 = 642 as desired
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)