Detailed mathematical approach

Problem Summary

This is a two-pile impartial game. After sorting each position so that \(a \le b\), a legal move subtracts a positive multiple of one of the vectors

$ (1,0),\ (0,1),\ (1,1),\ (1,2),\ (2,1), $

as long as both piles stay nonnegative; after the subtraction we sort again. Let \(P\)-positions be the losing positions. The target function is

$f(M)=\sum_{\substack{(a,b)\in P\\0\lt a+b\le M}} (a+b).$

A full dynamic program over all states with \(a+b\le 10^7\) would be far too slow, so the implementation constructs the losing positions directly.

Mathematical Approach

The terminal state \((0,0)\) is the first \(P\)-position. The nonzero \(P\)-positions are then generated in increasing order of the first coordinate.

Step 1: Why a Greedy Construction Is Plausible

Suppose two losing positions shared a positive coordinate. For example, if \((c,d)\) and \((c,e)\) with \(d\lt e\) were both losing, then the larger one could move to the smaller one by subtracting \(e-d\) from a single pile. That is impossible for two \(P\)-positions.

So every positive integer can appear in at most one coordinate among the nonzero losing pairs. This suggests the usual Wythoff-style greedy rule:

take the smallest positive integer not used yet as the next first coordinate \(x\), then choose the smallest \(y\gt x\) that is not attacked by any earlier losing pair.

The implementations follow exactly this rule, and they verify it against brute force for small bounds.

Step 2: Forbidden Invariants from Earlier Losing Pairs

Let \((a,b)\) be an earlier losing position with \(a\lt b\), and let \((x,y)\) be a new candidate with \(x\lt y\).

Axis moves already explain why \(x\) and \(y\) cannot reuse any earlier coordinate. The proportional moves give three more forbidden affine invariants.

If \((x,y)\) could reach \((a,b)\) by a diagonal move \((n,n)\), then

$x-a=n,\qquad y-b=n,$

so

$y-x=b-a.$

If \((x,y)\) could reach \((a,b)\) by a \((1,2)\)-type move without changing order after the subtraction, then

$x-a=n,\qquad y-b=2n,$

which is equivalent to

$y-2x=b-2a.$

If \((x,y)\) could reach \((a,b)\) by a \((2,1)\)-type move without changing order, then

$x-a=2n,\qquad y-b=n,$

which gives

$2y-x=2b-a.$

Therefore each earlier losing pair forbids one coordinate family and three affine families:

$y\notin U,\qquad y-x\notin D,\qquad y-2x\notin T,\qquad 2y-x\notin S.$

Step 3: Swaps Create Delayed Constraints

The two proportional moves have another possibility: after subtracting \((n,2n)\) or \((2n,n)\), the two coordinates may need to be swapped before we compare with \((a,b)\).

For a swapped \((1,2)\)-type move we must have

$x-n=b,\qquad y-2n=a,$

so the same candidate is forbidden when

$y-2x=a-2b.$

For a swapped \((2,1)\)-type move we get

$x-2n=b,\qquad y-n=a,$

hence

$2y-x=2a-b.$

These two extra affine values matter only when the new first coordinate has already passed the old second coordinate, namely when

$x\gt b.$

That is why the implementation does not insert them immediately. Instead it schedules them to become active starting at \(x=b+1\). This event mechanism is the key detail that keeps the greedy construction correct.

Step 4: Find the Smallest Valid \(y\) by Successor Queries

For any forbidden set \(F\), define the successor operator

$\operatorname{next}_F(t)=\min\{u\ge t:u\notin F\}.$

For a fixed first coordinate \(x\), the search starts at \(y=x+1\) and repeatedly pushes \(y\) upward until all constraints are satisfied:

$y\leftarrow \operatorname{next}_U(y),$

$y\leftarrow x+\operatorname{next}_D(y-x),$

$y\leftarrow 2x+\operatorname{next}_T(y-2x),$

and finally \(2y-x\) is pushed past the forbidden values in \(S\).

Each update only increases \(y\), so the process reaches a fixed point. That fixed point is the smallest admissible partner for \(x\), hence the next losing pair.

The quantity \(2y-x\) always has the same parity as \(x\). The implementation uses that fact to store the \(S\)-family in two parity classes, but mathematically it is still the single condition \(2y-x\notin S\).

Step 5: Worked Example for \(M=10\)

Start from the terminal position \((0,0)\). It already forbids the affine value \(0\) in the diagonal, \((1,2)\), and \((2,1)\) families.

For \(x=1\), the first candidate is \(y=2\). This fails because

$y-2x=2-2=0,$

which would allow the move \((1,2)\) to \((0,0)\). The next possibility is \(y=3\), which is valid, so the first nonzero losing pair is

$ (1,3). $

For \(x=2\), \(y=3\) is impossible because \(3\) is already used. Then \(y=4\) fails since

$y-x=2,$

matching the diagonal invariant from \((1,3)\). Next \(y=5\) fails because

$y-2x=1,$

matching the \((1,2)\)-invariant from \((1,3)\). Therefore the next valid pair is

$ (2,6). $

The coordinate \(x=3\) is skipped because it is already used. Before processing \(x=4\), the delayed constraints coming from \((1,3)\) become active since now \(x\gt 3\). The smallest valid partner is \(y=5\), giving

$ (4,5). $

These are exactly the losing pairs with sum at most \(10\), so

$f(10)=4+8+9=21,$

which matches the checkpoint used by the implementation.

How the Code Works

The C++, Python, and Java implementations all maintain the same logical state:

one successor structure for used coordinates, one for forbidden diagonal differences, one for forbidden values of \(y-2x\), and a parity-split representation of the forbidden values of \(2y-x\). They also maintain a min-priority queue of delayed affine constraints that will become active when \(x\) passes a stored threshold.

At each step, the implementation activates all events whose threshold has been reached, chooses the smallest unused \(x\), and then runs the fixed-point lifting process described above to obtain the smallest legal \(y\).

Once \((x,y)\) is accepted, both coordinates are marked as used. The immediate invariants

$b-a,\qquad b-2a,\qquad 2b-a$

for that new losing pair are inserted right away, and the swapped-case invariants

$a-2b,\qquad 2a-b$

are scheduled to activate starting at the first future step with \(x\gt b\).

If \(x+y\le M\), the pair contributes \(x+y\) to the answer. Otherwise it still matters structurally, because its coordinates and affine invariants can block later pairs whose first coordinate is still at most \(M\).

The implementations also include a small brute-force comparison against the win/lose dynamic program on tiny bounds, which is how the construction is sanity-checked.

Complexity Analysis

Let \(P(M)\) be the number of losing pairs generated before the first coordinate exceeds \(M\). Every generated pair causes a constant number of successor queries, a constant number of insertions, one event insertion, and later one event removal.

The successor structures use path compression, so their operations are amortized extremely close to constant time. The priority queue contributes a logarithmic factor. Therefore the overall running time is

$O\!\left(P(M)\log P(M)\right),$

with near-linear practical behavior. The memory usage is

$O\!\left(P(M)\right).$

Because no positive coordinate is ever reused, \(P(M)\) itself grows only linearly with the search range, which is why the method scales to the required bound.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=665
2. Wythoff's game: Wikipedia — Wythoff's game
3. Sprague-Grundy theorem: Wikipedia — Sprague-Grundy theorem
4. Minimum excluded value: Wikipedia — Minimum excludant
5. Disjoint-set data structure: Wikipedia — Disjoint-set data structure