Detailed mathematical approach

Problem Summary

Consider a two-pile impartial game with positive piles \((a,b)\). If we sort the position as

$m=\min(a,b),\qquad M=\max(a,b),$

then one legal move chooses an integer \(y\) with \(1\le y\le m\) and replaces the position by the positive pair \((y,M-y)\), reordering if necessary. Equivalently, every move keeps the larger pile's total \(M\) and repartitions it into two positive parts, with one chosen part not exceeding the old smaller pile.

The task is to count all losing positions with

$1\le a,b\le n,\qquad n=7^{17}.$

A direct dynamic program over the full \(n\times n\) grid is hopeless, so the solution depends on a closed binary characterization of the losing states.

Mathematical Approach

Write every position in sorted form \((m,M)\) with \(m\le M\). The key theorem is that the answer depends only on the bit-length of the smaller pile and one congruence class of the larger pile.

Step 1: Organize Positions by the Smaller Pile's Bit-Length

Let

$k=\lfloor \log_2 m\rfloor+1,\qquad p=2^k.$

Then \(m\) lies in the binary layer

$2^{k-1}\le m\le 2^k-1=p-1.$

The implementations use the following criterion:

$\boxed{(m,M)\text{ is losing }\Longleftrightarrow M\equiv p-1\pmod p.}$

So once the smaller pile is known, the larger pile must end with exactly \(k\) binary \(1\)-bits. The rest of the analysis is a proof of this statement and a count of how often it occurs.

Step 2: Why the Residue Class \(p-1\) Is Losing

Assume

$M\equiv p-1\pmod p.$

Take any legal move and sort the child position as \((u,v)\) with \(u\le v\). Because a move repartitions \(M\), we always have

$u+v=M,\qquad 1\le u<p.$

Now let

$q=2^{\lfloor \log_2 u\rfloor+1}.$

Since \(u<p\), its bit-length is at most \(k\), so \(q\mid p\). If the child were losing, then the same criterion at the smaller scale would force

$v\equiv q-1\pmod q.$

But \(M\equiv p-1\pmod p\) implies \(M\equiv q-1\pmod q\) as well, because \(q\mid p\). Therefore

$u=M-v\equiv (q-1)-(q-1)\equiv 0\pmod q.$

This is impossible: by definition of \(q\), the smaller number \(u\) satisfies

$0<u<q.$

So no legal move can reach a losing child. Hence every position with \(M\equiv p-1\pmod p\) is itself losing.

Step 3: Why Every Other Residue Class Is Winning

Now assume

$M\not\equiv p-1\pmod p.$

Define the nonzero residue

$t=(M+1)\bmod p,\qquad 1\le t\le p-1,$

and let \(y\) be the lowest power of two dividing \(t\):

$y=2^{\nu_2(t)}.$

Because \(t<p=2^k\), this power satisfies

$y\le 2^{k-1}\le m,$

so moving to \((y,M-y)\) is legal. Write

$M+1=cp+t,\qquad t=y(2s+1)$

for integers \(c\ge 0\) and \(s\ge 0\). Then

$M-y=cp+t-1-y=cp+2sy+y-1.$

This is at least \(y\): the only way \(cp+2sy-1\) could be negative is \(c=s=0\), which would give \(M=y-1\), contradicting \(y\le m\le M\). Therefore the child really has smaller pile \(y\).

Also, because \(t/y\) is odd,

$t\equiv y\pmod{2y},$

hence

$M-y\equiv -1\pmod{2y}.$

The smaller pile of the child is \(y\), whose bit-length corresponds exactly to modulus \(2y\). So the child satisfies the losing criterion. Every position outside the residue class \(p-1\) therefore has a move to a losing state and is winning.

Step 4: Count Losing Positions in One Binary Layer

Fix \(k\), so \(p=2^k\). The smaller pile can take any value in

$2^{k-1}\le m\le \min(n,p-1).$

The number of available smaller piles in this layer is

$A_k=\min(n,p-1)-2^{k-1}+1.$

For each such \(m\), the larger pile must satisfy

$M\equiv p-1\pmod p,\qquad M\le n.$

Those values are

$p-1,\ 2p-1,\ 3p-1,\ \dots,$

so their count is

$C_k=\left\lfloor\frac{n+1}{p}\right\rfloor=\left\lfloor\frac{n+1}{2^k}\right\rfloor.$

Notice that every such \(M\) is at least \(p-1\), while every \(m\) in the same layer is at most \(p-1\). Thus the ordering condition \(m\le M\) holds automatically. The number of losing unordered pairs contributed by layer \(k\) is therefore

$A_k\,C_k.$

Step 5: Sum the Layers and Correct for Order

Let \(U(n)\) be the number of losing unordered pairs \((m,M)\) with \(m\le M\). Summing the layers gives

$U(n)=\sum_{k\ge 1,\ 2^{k-1}\le n} \left(\min(n,2^k-1)-2^{k-1}+1\right)\left\lfloor\frac{n+1}{2^k}\right\rfloor.$

The final answer counts ordered pairs \((a,b)\), not just sorted ones. Off-diagonal positions contribute twice, but diagonal positions \((x,x)\) should be counted only once. A diagonal pair is losing exactly when

$x\equiv 2^k-1\pmod{2^k}$

with \(x<2^k\), which forces

$x=2^k-1.$

So the diagonal losing positions are precisely the Mersenne numbers not exceeding \(n\), and their count is

$D(n)=\#\{k\ge 1:2^k-1\le n\}=\lfloor \log_2(n+1)\rfloor.$

Hence the required count of ordered losing positions is

$\boxed{L(n)=2U(n)-D(n).}$

Worked Example: \(n=7\)

For \(n=7\) there are three nonempty layers.

For \(k=1\), we have \(m=1\), so \(A_1=1\), and the valid larger piles are \(1,3,5,7\), hence \(C_1=4\).

For \(k=2\), the smaller pile lies in \(\{2,3\}\), so \(A_2=2\), and the valid larger piles are \(3,7\), hence \(C_2=2\).

For \(k=3\), the smaller pile lies in \(\{4,5,6,7\}\), so \(A_3=4\), and the only valid larger pile is \(7\), hence \(C_3=1\).

Therefore

$U(7)=1\cdot 4+2\cdot 2+4\cdot 1=12.$

The diagonal losing positions are \((1,1)\), \((3,3)\), and \((7,7)\), so \(D(7)=3\). Thus

$L(7)=2\cdot 12-3=21,$

which matches the small verification used by the implementations.

How the Code Works

The C++, Python, and Java implementations all evaluate the same closed formula. They first compute \(n=7^{17}\). Then they iterate over bit-length layers \(k=1,2,\dots\) until \(2^{k-1}>n\). In each layer they compute the interval of possible smaller piles, convert it into \(A_k\), compute the number \(C_k\) of valid larger piles with residue \(2^k-1\), and add the product \(A_kC_k\) to the unordered total.

After that, they count the diagonal corrections \(2^k-1\le n\) and combine everything as \(2U(n)-D(n)\). The C++ implementation additionally builds a small brute-force game table for tiny bounds and checks that the binary criterion reproduces every losing position there; the large input itself is handled purely by the closed formula.

Complexity Analysis

The main computation only iterates over powers of two, so it uses \(O(\log n)\) time and \(O(1)\) extra memory. The optional small validation table in the C++ version is cubic-time in the test bound and quadratic-memory, but it is used only for tiny sanity checks and does not affect the asymptotic cost of solving the actual problem.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=899
2. Impartial game: Wikipedia - Impartial game
3. Binary number: Wikipedia - Binary number
4. Mersenne number: Wikipedia - Mersenne number
5. \(p\)-adic valuation: Wikipedia - \(p\)-adic valuation