Mex Sequence

In this problem $\oplus$ is used to represent the bitwise exclusive or of two numbers.
Starting with blank paper repeatedly do the following:

Write down the smallest positive integer $a$ which is currently not on the paper;
Find the smallest positive integer $b$ such that neither $b$ nor $(a \oplus b)$ is currently on the paper. Then write down both $b$ and $(a \oplus b)$.

After the first round $\{1,2,3\}$ will be written on the paper. In the second round $a=4$ and because $(4 \oplus 5)$, $(4 \oplus 6)$ and $(4 \oplus 7)$ are all already written $b$ must be $8$.

After $n$ rounds there will be $3n$ numbers on the paper. Their sum is denoted by $M(n)$.
For example, $M(10) = 642$ and $M(1000) = 5432148$.

Find $M(10^{18})$. Give your answer modulo $1\,000\,000\,007$.

In order to find the solution, it’s useful to observe how the numbers b and a⊕b are generated for each round n. This is to figure out their relationship with round number n.

After analyzing the numbers generated for each round, you would find the pattern that, for each round i, the number b is 2i. The number a⊕b would then be twice the number b (or 4i) minus 1, because XORing a number with itself halves the value, and since a is 2i — 1, a XOR b will therefore be 4i — 1.

The total sum of numbers written in each round i (a + b + a⊕b) will be 7i.

Now, if we sum over all rounds from i = 1 to n, we could find M(n) as:

M(n) = Σ(7i) for i from 1 to n = 7 * Σ(i) for i from 1 to n = 7 * (n*(n+1))/2

These are using basic summation rules, which are Σ(i) for i from 1 to n = (n*(n+1))/2.

Finally, because the problem asks for an answer mod 1,000,000,007, we need to take the result of the previous computation mod 1,000,000,007.

Finding values modulo a number can be simplified with certain operations. For example, (a*b)mod m = [(a mod m) * (b mod m)] mod m. This is because modulo operation distributes over product operation.

Therefore, M(n) mod 1,000,000,007 = (n mod 1,000,000,007 * (n+1) mod 1,000,000,007 * 7 mod 1,000,000,007/2 mod 1,000,000,007) mod 1,000,000,007.

Essentially, we are taking each part of the computation and finding its value mod 1,000,000,007, then multiplying them together and finally finding that product’s value mod 1,000,000,007.
This can help you with multi-step computations modulo a large number, which may be difficult to compute directly.

NOTE: Due to the size of the numbers involved (n = 10^18), to evaluate this expression a software tool capable of handling large precision arithmetic, like Python, should be used. Be aware of overflow issues that may occur with large integers in other programming languages.

More Answers: