Detailed mathematical approach

Problem Summary

In Nim Square, a move on one heap of size \(n\) removes any positive square \(k^2\le n\). The position has three heaps, and we must count how many ordered-by-size triples

$0\le a\le b\le c\le N$

are losing positions.

Mathematical Approach

1) Single-heap Grundy numbers

For one heap, the legal moves are

$n\to n-1,\ n-4,\ n-9,\dots$

for every square not exceeding \(n\). So the Grundy value of a single heap is

$g(0)=0,$

$g(n)=\operatorname{mex}\{g(n-k^2):k^2\le n\}.$

This is the usual subtract-a-square recurrence.

2) Why three heaps reduce to xor

The full game is the disjoint sum of three impartial subgames. Therefore Sprague-Grundy theory says that the triple \((a,b,c)\) is losing exactly when the nim-sum vanishes:

$g(a)\oplus g(b)\oplus g(c)=0.$

So once the array \(g(0),\dots,g(N)\) is known, the entire counting problem becomes a combinatorial xor-counting problem.

3) Small worked example

The first few single-heap values are

$g(0..4)=(0,1,0,1,2).$

For instance:

$g(1)=\operatorname{mex}\{g(0)\}=\operatorname{mex}\{0\}=1,$

$g(2)=\operatorname{mex}\{g(1)\}=\operatorname{mex}\{1\}=0,$

$g(4)=\operatorname{mex}\{g(3),g(0)\}=\operatorname{mex}\{1,0\}=2.$

If \(N=4\), the losing triples are

$\begin{aligned} &(0,0,0),(0,0,2),(0,1,1),(0,1,3),(0,2,2),(0,3,3),\\ &(0,4,4),(1,1,2),(1,2,3),(2,2,2),(2,3,3),(2,4,4), \end{aligned}$

so the count is \(12\).

4) The naive count is cubic

A direct scan over all triples \((a,b,c)\) would take

$O(N^3)$

time, which is impossible for \(N=100000\). The code instead reorganizes the count by fixing the middle heap \(b\).

5) Prefix/suffix counting for a fixed middle heap

Fix \(b\). Then:

Left side: \(a\) may range over \(0\le a\le b\).

Right side: \(c\) may range over \(b\le c\le N\).

Let

$\text{pref}[x]=\#\{a\le b:g(a)=x\},$

$\text{suf}[y]=\#\{c\ge b:g(c)=y\}.$

For a fixed Grundy value \(x=g(a)\), the losing condition

$x\oplus g(b)\oplus g(c)=0$

forces

$g(c)=x\oplus g(b).$

Hence the number of losing triples with this middle value \(b\) is

$\text{add}_b=\sum_x \text{pref}[x]\cdot \text{suf}[x\oplus g(b)].$

Summing \(\text{add}_b\) over all \(b\) gives the final answer.

6) Why this automatically respects \(a\le b\le c\)

The implementation maintains the arrays in a very specific order:

Before counting for \(b\): it adds \(g(b)\) to the prefix array.

During counting: prefix therefore represents \(a\in[0,b]\), while suffix still represents \(c\in[b,N]\).

After counting: it removes \(g(b)\) from suffix, so the next step uses \(c\ge b+1\).

This means the ordering constraint is built directly into the data structure update order; no extra combinatorial correction is needed.

How the Code Works

1) Build Grundy table. build_grundy(limit) computes the subtract-a-square Grundy values using a timestamp-based mex array.

2) Determine Grundy alphabet size. The code records

$\max g(n)$

so it knows how large the prefix and suffix frequency arrays must be.

3) Initialize suffix. Initially all heaps \(0,\dots,N\) are available on the right, so suffix counts every Grundy value in the full range.

4) Sweep the middle index. For each \(b\), the code updates prefix, applies the xor-count formula above, then removes \(b\) from suffix.

5) Checkpoints. The C++ version verifies

$\texttt{solve(29)}=1160$

and also checks that \(\texttt{solve(40)}\) matches a literal brute-force triple scan.

6) Final Project Euler value. For the required bound \(N=100000\), the implementation returns

$2586528661783.$

Complexity Analysis

Computing the Grundy table costs about \(O(N\sqrt N)\), because each \(g(n)\) examines all squares up to \(n\). The counting sweep costs \(O(N\cdot G)\), where \(G\) is the number of distinct Grundy values encountered, which stays small in practice. Memory usage is \(O(N+G)\).

Further Reading

1. Problem page: https://projecteuler.net/problem=310
2. Sprague-Grundy theorem: https://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem
3. Subtract-a-square game: https://en.wikipedia.org/wiki/Subtract_a_square