Detailed mathematical approach

Problem Summary

We build a set in rounds. At round \(r\), let \(a_r\) be the smallest positive integer not yet present. Then choose the smallest positive integer \(b_r\) such that both \(b_r\) and \(c_r=a_r\oplus b_r\) are still absent, and insert the triple \((a_r,b_r,c_r)\). If \(P_r\) denotes the set after \(r\) rounds, the target quantity is

$M(r)=\sum_{x\in P_r} x,$

with the final answer required modulo \(10^9+7\).

A direct simulation is hopeless for \(r=10^{18}\). The implementations therefore avoid storing the set explicitly and instead exploit a rigid 4-way self-similar structure hidden inside the generated triples.

Mathematical Approach

Write the construction as

$P_0=\varnothing,$

$a_r=\operatorname{mex}(P_{r-1}),$

$b_r=\min\{b\ge 1:\ b\notin P_{r-1},\ a_r\oplus b\notin P_{r-1}\},$

$c_r=a_r\oplus b_r,$

$P_r=P_{r-1}\cup\{a_r,b_r,c_r\}.$

The key is that the rounds do not behave randomly: they fall into blocks of lengths \(1,4,16,64,\dots\), and each block is built from four smaller copies of the same pattern.

Step 1: Complete Blocks Restore a Contiguous Prefix

Let

$T_k=1+4+4^2+\cdots+4^k=\frac{4^{k+1}-1}{3}.$

The observed and implemented block theorem is:

After exactly \(T_k\) rounds, the set of inserted numbers is

$P_{T_k}=\{1,2,3,\dots,4^{k+1}-1\}.$

This is true for \(k=0\), because the first round inserts \((1,2,3)\). If a block of size \(s\) contributes exactly the three disjoint intervals

$[a,a+s-1],\qquad [b,b+s-1],\qquad [c,c+s-1],$

then the special outer blocks use the seeds

$ (s,2s,3s),\qquad s=1,4,16,\dots $

and therefore fill

$[s,2s-1]\cup[2s,3s-1]\cup[3s,4s-1]=[s,4s-1].$

Since all earlier completed blocks already filled \([1,s-1]\), the union becomes \([1,4s-1]\). Hence the next mex is \(4s\), so the next complete block must start at \((4s,8s,12s)\).

Step 2: One Block Splits into Four Quarter-Blocks

Consider a block of size \(s=4^m\) with seed triple \((a,b,c)\). When \(s=1\), the block is just that single triple. For \(s>1\), set

$q=\frac{s}{4}.$

The block is the ordered concatenation of four child blocks of size \(q\):

$ (a,b,c),\quad (a+q,b+2q,c+3q),\quad (a+2q,b+3q,c+q),\quad (a+3q,b+q,c+2q). $

Each child has the same internal structure as the parent, only scaled down by a factor of \(4\). This is the fundamental self-similarity exploited by the algorithm.

Step 3: Why the XOR Condition Survives the Split

The quarter-block offsets are not arbitrary. Their leading base-4 digits are

$ (0,0,0),\qquad (1,2,3),\qquad (2,3,1),\qquad (3,1,2). $

In every case, the third digit is the bitwise XOR of the first two:

$0\oplus 0=0,\qquad 1\oplus 2=3,\qquad 2\oplus 3=1,\qquad 3\oplus 1=2.$

Because \(q\) is a power of \(4\), adding a multiple of \(q\) changes a fresh pair of bits and does not interfere with the lower bits handled inside the recursive child. So if a parent block respects \(c=a\oplus b\), then each child block also respects the same relation after its offset is applied.

This is the reason the same pattern can repeat indefinitely across scales.

Step 4: A Full Block Is Just Three Arithmetic Progressions

Although the triples inside a block are interleaved, the set of first coordinates over the whole block is exactly

$a,a+1,\dots,a+s-1,$

the set of second coordinates is exactly

$b,b+1,\dots,b+s-1,$

and the set of third coordinates is exactly

$c,c+1,\dots,c+s-1.$

Therefore the contribution of the entire block is

$B(a,b,c;s)=\sum_{t=0}^{s-1}(a+t)+(b+t)+(c+t).$

Equivalently,

$B(a,b,c;s)=\frac{s(2a+s-1)+s(2b+s-1)+s(2c+s-1)}{2}.$

This closed form is why completed blocks can be consumed instantly instead of round by round.

Step 5: Prefixes of a Block Are Computed Recursively

Now suppose we need only the first \(\ell\) rounds of a block of size \(s=4q\). Let

$\ell_1=\min(\ell,q),$

$\ell_2=\min(\max(\ell-q,0),q),$

$\ell_3=\min(\max(\ell-2q,0),q),$

$\ell_4=\min(\max(\ell-3q,0),q).$

Then the prefix sum is the sum of four child-prefix sums, taken in order:

$ P(\ell;a,b,c;s)=P(\ell_1;a,b,c;q)+P(\ell_2;a+q,b+2q,c+3q;q) $

$ \hphantom{P(\ell;a,b,c;s)=}\ +P(\ell_3;a+2q,b+3q,c+q;q)+P(\ell_4;a+3q,b+q,c+2q;q). $

The base cases are immediate: an empty prefix contributes \(0\), a full prefix contributes \(B(a,b,c;s)\), and a block of size \(1\) contributes \(a+b+c\).

Step 6: Worked Example for \(n=10\)

The block sizes are \(1,4,16,\dots\). So the first \(10\) rounds consist of

one full block of size \(1\),

one full block of size \(4\),

and the first \(5\) rounds of the next block of size \(16\).

The size-\(1\) block is just

$ (1,2,3), $

so its contribution is \(6\).

The next block has seed \((4,8,12)\) and size \(4\). Its four rounds are

$ (4,8,12),\quad (5,10,15),\quad (6,11,13),\quad (7,9,14), $

which together insert every integer from \(4\) to \(15\). Hence that full block contributes

$4+5+\cdots+15=114.$

The next block has seed \((16,32,48)\) and size \(16\). The first quarter is a full child block of size \(4\), so it contributes

$ (16+17+18+19)+(32+33+34+35)+(48+49+50+51)=402. $

One more round is needed, namely the first round of the second quarter-block, which is \((20,40,60)\) and contributes \(120\).

Therefore

$M(10)=6+114+402+120=642,$

matching the checkpoint used by the implementations.

How the Code Works

The C++, Python, and Java implementations all follow the same strategy.

First, they peel off complete outer blocks of sizes \(1,4,16,\dots\). For each completed block they add the arithmetic-progression formula above, then move to the next seed \((4a,4b,4c)\) and the next block size \(4s\).

Once the remaining number of rounds fits inside the current block, the implementation switches to a recursive prefix evaluator. That routine walks the four quarter-blocks in order, adds a full quarter immediately when it is completely covered, skips a quarter when it is untouched, and descends only into the quarter that is partially covered.

All arithmetic is performed modulo \(10^9+7\). The sum of an arithmetic progression is evaluated safely modulo that prime by multiplying with the modular inverse of \(2\), so no floating-point arithmetic is needed.

Complexity Analysis

The outer block loop touches block sizes \(1,4,16,\dots\), so it takes \(O(\log_4 n)\) iterations. The recursive prefix computation descends through at most one genuinely partial branch per level and performs only constant extra work around it. Therefore the total running time is \(O(\log n)\).

The only non-constant auxiliary memory is the recursion stack, whose depth is also \(O(\log n)\). No explicit set of inserted numbers is stored.

Footnotes and References

1. Problem page: Project Euler 832
2. Mex operator: Wikipedia - Mex (mathematics)
3. Exclusive OR: Wikipedia - Exclusive or
4. Arithmetic progression: Wikipedia - Arithmetic progression
5. Divide and conquer: Wikipedia - Divide-and-conquer algorithm