Detailed mathematical approach

Problem Summary

For each starting value \(r\), the game distinguishes moves by the parity of the Hamming weight of the chosen subtraction:

$t(x)=\operatorname{popcount}(x)\bmod 2.$

The goal is to sum all \(r\in[1,2^n]\) for which Oscar loses with perfect play. The brute-force dynamic program in the implementations confirms the game rules for small \(n\), while the production solver exploits a rigid base-4 layer structure and works modulo \(10^9+7\).

Mathematical Approach

The fast solution comes from understanding which positions are losing, not from simulating every move up to \(2^n\).

Step 1: Encode the Game with Four Minimax States

For a remaining value \(r\), the brute-force derivation tracks two pieces of information: whose turn it is, and a binary flag \(q\in\{0,1\}\) that records the running parity relevant to the win condition. Let

$O_q(r)\in\{0,1\}$

mean “Oscar wins from remainder \(r\) when it is Oscar's turn and the flag is \(q\),” and let

$E_q(r)\in\{0,1\}$

mean the same when it is Eric's turn.

At \(r=0\), no move is possible, so the terminal outcome is determined only by the flag:

$O_0(0)=E_0(0)=0,\qquad O_1(0)=E_1(0)=1.$

For \(r>0\), every legal move chooses some \(x\in[1,r]\), changes the flag by \(t(x)\), and leaves remainder \(r-x\). Oscar uses existential choice, Eric universal choice, so

$O_q(r)=\bigvee_{x=1}^{r} E_{q\oplus t(x)}(r-x),\qquad E_q(r)=\bigwedge_{x=1}^{r} O_{q\oplus t(x)}(r-x).$

The starting position for a given number \(r\) is \(O_{t(r)}(r)\). Therefore \(r\) contributes to the required sum exactly when \(O_{t(r)}(r)=0\).

Step 2: Reduce the Four States to Two Losing Sets

The four-state system collapses neatly. From the recurrence above, one obtains

$E_0(r)=1-O_1(r),\qquad E_1(r)=1-O_0(r).$

So it is enough to study the two Oscar-to-move losing sets

$L_0=\{r\ge 0: O_0(r)=0\},\qquad L_1=\{r\ge 0: O_1(r)=0\}.$

The final answer is the sum over

$L=\{r\ge 1: r\in L_{t(r)}\}.$

This already matches the brute-force tables: the implementation computes the four boolean state arrays, but the actual losing positions depend only on which of the two parity-indexed Oscar states fails.

Step 3: Split the Number Line into Base-4 Layers

The parity sequence \(t(x)\) is the Thue-Morse sequence, and powers of \(4\) are the natural scale because

$t(4^k+y)=1\oplus t(y),\qquad t(2\cdot 4^k+y)=1\oplus t(y),\qquad t(3\cdot 4^k+y)=t(y).$

Digits \(1\) and \(2\) in base \(4\) contribute odd popcount parity, while digits \(0\) and \(3\) contribute even parity. This is why the losing pattern repeats blockwise.

Now partition the positive integers into alternating base-4 layers:

$I_k^{\mathrm{even}}=[4^k,\,2\cdot 4^k-1],\qquad I_k^{\mathrm{odd}}=[2\cdot 4^k,\,4^{k+1}-1].$

The exact pattern revealed by the brute-force tables and used by the fast solver is:

$I_k^{\mathrm{odd}}\cap L=\{4^{k+1}-1\},$

and for the even layers there exists an offset set \(E_k\subseteq[0,4^k-1]\) such that

$I_k^{\mathrm{even}}\cap L=\{4^k+e:\ e\in E_k\},\qquad E_0=\{0\}.$

The first few offset sets are

$E_0=\{0\},\qquad E_1=\{0,3\},\qquad E_2=\{0,3,4,15\},\qquad E_3=\{0,3,4,15,16,19,20,63\}.$

Step 4: Derive the Offset Recurrence

When we pass from the even layer at scale \(4^k\) to the next even layer at scale \(4^{k+1}\), the losing offsets follow a precise self-similar rule:

$E_{k+1}=E_k\ \cup\ \left(4^k+\bigl(E_k\setminus\{4^k-1\}\bigr)\right)\ \cup\ \{4^{k+1}-1\}.$

Informally, one copy of the previous offsets survives unchanged, another copy is shifted by \(4^k\), and the old extreme point \(4^k-1\) is replaced by the new odd-layer endpoint \(4^{k+1}-1\).

Define

$N_k=|E_k|,\qquad T_k=\sum_{e\in E_k} e.$

Then \(N_0=1\), \(T_0=0\), and the set recurrence gives

$N_{k+1}=2N_k,$

$T_{k+1}=T_k+\left((N_k-1)4^k+T_k-(4^k-1)\right)+(4^{k+1}-1)=2T_k+(N_k+2)4^k.$

Hence

$N_k=2^k,$

which is exactly the doubling behavior used by the linear solver.

Step 5: Turn the Structure into a Sum Formula

The total contribution of the even layer \(I_k^{\mathrm{even}}\) is

$\sum_{e\in E_k}(4^k+e)=N_k4^k+T_k.$

The total contribution of the odd layer \(I_k^{\mathrm{odd}}\) is simply

$4^{k+1}-1.$

Therefore the answer is obtained by scanning the layers from left to right. If \(n\) is even, the endpoint \(2^n=4^{n/2}\) belongs to the next even layer and must be added separately. This is why the final formula in the implementation has a last \(2^n\) correction exactly when \(n\) is even.

Worked Example: \(n=6\)

Here we need all losing positions in \([1,64]\).

The odd layers contribute only their endpoints:

$3,\qquad 15,\qquad 63.$

The even layers are built from the offset sets:

$1+E_0=\{1\},\qquad 4+E_1=\{4,7\},\qquad 16+E_2=\{16,19,20,31\}.$

Because \(n=6\) is even, we also add the endpoint

$2^6=64.$

So the losing positions are

$1,3,4,7,15,16,19,20,31,63,64,$

and their sum is

$1+3+4+7+15+16+19+20+31+63+64=243.$

This matches the brute-force dynamic program.

How the Code Works

The C++, Python, and Java implementations all use the same fast layer recurrence. They iterate once over the layer index, maintain the current number of even-layer offsets, the sum of those offsets, and the current power \(4^k\), and then add either

$N_k4^k+T_k$

for an even layer or

$4^{k+1}-1$

for an odd layer. After every even layer, the offset statistics are updated with

$N_{k+1}=2N_k,\qquad T_{k+1}=2T_k+(N_k+2)4^k.$

At the end, if \(n\) is even, the implementation adds \(2^n\) with modular exponentiation. The C++ version also contains a brute-force verifier for small exponents and checks the recurrence against known checkpoints such as \(n=4\mapsto 46\) and \(n=12\mapsto 54532\).

Complexity Analysis

The brute-force verifier fills game states for every \(r\le 2^n\) and scans every legal move \(x\le r\), so its running time is \(O(4^n)\) and its memory use is \(O(2^n)\). The optimized solver never expands the position graph. It performs one constant-time update per layer, so it runs in \(O(n)\) time and \(O(1)\) memory.

Footnotes and References

1. Problem page: Project Euler 711 - Binary Blackboard
2. Combinatorial game theory: Wikipedia - Combinatorial game theory
3. Minimax reasoning in finite games: Wikipedia - Minimax
4. Thue-Morse sequence: Wikipedia - Thue-Morse sequence
5. Hamming weight: Wikipedia - Hamming weight