Detailed mathematical approach

Problem Summary

For a fixed \(n\), the game positions are the coprime ordered pairs \((a,b)\) of positive integers with \(a+b\le n\). A legal move goes to a smaller positive pair \((u,v)\) satisfying

$1\le u<a,\qquad 1\le v<b,\qquad |av-bu|=1.$

The game convention used here treats every position with \(a=1\) or \(b=1\) as an immediate win. The goal is to count how many admissible positions are winning when \(n=10^9\).

Mathematical Approach

Let \(W(n)\) be the number of winning positions and \(T(n)\) the number of all primitive positions. The fast solution first counts every primitive pair, then subtracts the pairs that are losing.

Step 1: Count All Primitive Positions

Fix the sum \(s=a+b\). Then \(1\le a\le s-1\) and \(b=s-a\), so

$\gcd(a,b)=\gcd(a,s).$

Therefore the number of coprime ordered pairs with \(a+b=s\) is exactly \(\varphi(s)\). Summing over every possible total gives

$T(n)=\sum_{s=2}^{n}\varphi(s)=\Phi(n)-1,$

where

$\Phi(n)=\sum_{m\le n}\varphi(m).$

The implementations evaluate \(\Phi(n)\) through the standard Möbius identity

$\Phi(n)=\frac{1+\sum_{d=1}^{n}\mu(d)\left\lfloor\frac{n}{d}\right\rfloor^2}{2},$

which turns the problem into prefix queries for the Möbius function.

Step 2: Characterize the Losing Positions

Because the move rule is symmetric in \(a\) and \(b\), it is enough to understand the ordered half \(1<a<b\). Consider such a state and one of its legal children \((u,v)\). From

$av-bu=\pm1$

we obtain

$v-u=\frac{(b-a)u\pm1}{a}\ge 0.$

So every child also lies in the ordered half, except for the boundary case \((u,v)=(1,1)\), which is already a base win.

Now argue by induction on \(a+b\):

If \(a\) is even, then \(b\) is odd because \(\gcd(a,b)=1\). Reducing \(av-bu=\pm1\) modulo \(2\) gives \(u\equiv1\pmod 2\). Hence every child has odd smaller coordinate, so no child belongs to the losing family described below. Therefore the state is losing.

If \(a\) is odd and \(a>1\), the congruences \(bu\equiv \pm1\pmod a\) give two residues \(u\) and \(a-u\) in \(\{1,\dots,a-1\}\). Since \(a\) is odd, exactly one of them is even. Choosing that even residue produces a legal child with \(u<v\) and, by parity, \(v\) odd. Its smaller coordinate is even, so by induction that child is losing. Therefore the original state is winning.

Thus the losing positions in the ordered half are exactly the primitive pairs

$ (a,b)=(2x,\,2y+1),\qquad 1\le x\le y,\qquad \gcd(2x,2y+1)=1. $

Step 3: Count the Ordered Losing Shape Without the Coprime Condition

Define \(A(q)\) to be the number of pairs of the form \((2x,2y+1)\) with \(1\le x\le y\) and \(2x+2y+1\le q\), ignoring coprimality for the moment. Set

$s=\left\lfloor\frac{q-1}{2}\right\rfloor.$

Then the constraints become

$1\le x\le y,\qquad x+y\le s.$

For fixed \(x\), the variable \(y\) runs from \(x\) to \(s-x\), so

$A(q)=\sum_{x=1}^{\lfloor s/2\rfloor}(s-2x+1).$

This simplifies to the closed form

$A(q)= \begin{cases} p^2, & s=2p,\\ p(p+1), & s=2p+1. \end{cases}$

An equivalent version, closer to the implementation, is obtained from \(k=\left\lceil q/2\right\rceil\) and \(p=\left\lfloor k/2\right\rfloor\):

$A(q)= \begin{cases} p^2, & k\text{ is odd},\\ p(p-1), & k\text{ is even}. \end{cases}$

Step 4: Enforce Coprimality with Möbius Inversion Over Odd Divisors

Every pair counted by \(A(q)\) has one even coordinate and one odd coordinate, so any common divisor must itself be odd. That makes the Möbius inversion especially clean:

$L_{1/2}(n)=\sum_{\substack{d\le n\\ d\text{ odd}}}\mu(d)\,A\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right),$

where \(L_{1/2}(n)\) is the number of losing positions in the ordered half \(a<b\).

To evaluate this quickly, define the ordinary Mertens function

$M(x)=\sum_{m\le x}\mu(m)$

and the odd-only prefix

$M_{\mathrm{odd}}(x)=\sum_{\substack{d\le x\\ d\text{ odd}}}\mu(d).$

The implementations use the identity

$M_{\mathrm{odd}}(x)=\sum_{j\ge0} M\!\left(\left\lfloor\frac{x}{2^j}\right\rfloor\right),$

which follows by expanding the right-hand side and observing that the contributions of even integers cancel in pairs, leaving only odd divisors.

Step 5: Use Symmetry and Assemble the Final Formula

Swapping coordinates preserves both the move rule and the winning/losing status. Since primitive pairs never lie on the diagonal except for \((1,1)\), which is already winning, the total number of losing positions is

$L(n)=2L_{1/2}(n).$

Therefore

$\boxed{W(n)=\left(\sum_{s=2}^{n}\varphi(s)\right)-2\sum_{\substack{d\le n\\ d\text{ odd}}}\mu(d)\,A\!\left(\left\lfloor\frac{n}{d}\right\rfloor\right).}$

This is exactly the arithmetic formula implemented by the fast solution.

Worked Example: \(n=20\)

First count all primitive states:

$T(20)=\sum_{s=2}^{20}\varphi(s)=127.$

Now count the ordered losing shape without enforcing coprimality. Here

$A(20)=20,$

coming from the twenty ordered pairs \((2x,2y+1)\) with \(2x<2y+1\) and \(2x+2y+1\le20\).

Among these, the only non-primitive family with odd gcd comes from \(d=3\), because

$A\!\left(\left\lfloor\frac{20}{3}\right\rfloor\right)=A(6)=1,$

while \(A(\lfloor20/d\rfloor)=0\) for every larger odd \(d\). Hence

$L_{1/2}(20)=A(20)-A(6)=20-1=19,$

$L(20)=2\cdot19=38,$

and finally

$W(20)=127-38=89.$

This matches direct recursive play on the small instance.

How the Code Works

The C++, Python, and Java implementations all follow the same numerical plan. They first build a presieved Möbius table up to a fixed bound and store its prefix sums. That gives instant access to \(M(x)\) for small \(x\).

For larger arguments, the implementation uses the classical divisor-block recurrence

$M(x)=1-\sum_{l=2}^{x}(r-l+1)\,M\!\left(\left\lfloor\frac{x}{l}\right\rfloor\right),$

where each block \([l,r]\) shares the same quotient \(\left\lfloor x/l\right\rfloor\). Memoization ensures that every large prefix value is computed only once.

The total number of primitive states is then obtained from the summatory-totient identity by grouping equal values of \(\left\lfloor n/d\right\rfloor\). The losing half is evaluated with the same quotient blocking, but using prefix differences of \(M_{\mathrm{odd}}\) and the explicit closed form for \(A(q)\).

After doubling the ordered-half losing count, the implementation subtracts it from the total primitive count. One version also checks the formula on small inputs with direct recursion before printing the large answer, but the actual \(n=10^9\) computation is purely arithmetic.

Complexity Analysis

Let \(B\) be the presieve limit. Building the Möbius sieve and its prefix sums costs \(O(B)\) time and \(O(B)\) memory. The outer summations for both the totient total and the losing count run over the distinct values of \(\left\lfloor n/d\right\rfloor\), which is \(O(\sqrt n)\).

The expensive part is answering large Mertens-prefix queries. Because those queries are memoized and each one is decomposed into quotient blocks as well, the practical running time stays far below linear in \(n\). Memory usage is dominated by the presieve arrays plus the cache of already-computed prefix values.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=787
2. Euler's totient function: Wikipedia — Euler's totient function
3. Möbius function: Wikipedia — Möbius function
4. Mertens function: Wikipedia — Mertens function
5. Möbius inversion formula: Wikipedia — Möbius inversion formula
6. Farey sequence: Wikipedia — Farey sequence