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
1. Hence b = 2, c = 3
2. Total = 6
When a = 4, 5, 6, 7, with i = 1 we have case 1, 2, 3, 4 respectively
1. 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)
2. Total = 114
When a = 16, 17, 18, 19, with i = 2 we have case 1
1. Hence b = 32, 33, 34, 35, and c = 38, 39, 50, 51 (Note that the order is no longer necessarily correct)
2. Total = 402
When a = 20, with i = 2 we have case 2
1. 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
2. Now we reduce this block of 4 to a lower power, that is i = 1
3. Then we know we are in case 1 again, hence we know b = 0 + 40, and c = 0 + 60
4. 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)

Page updated

Google Sites

Report abuse