Project Euler

Nim Square

Alice and Bob play Nim Square, which is like ordinary three-heap normal play Nim, but players may only remove a perfect square number of stones from a heap. A position (a, b, c) is losing for the n...

Source sync Apr 19, 2026

Problem #0310

Level Level 13

Solved By 1,388

Languages C++, Python

Answer 2586528661783

Length 334 words

game_theorylinear_algebrabrute_force

Alice and Bob play the game Nim Square.

Nim Square is just like ordinary three-heap normal play Nim, but the players may only remove a square number of stones from a heap.

The number of stones in the three heaps is represented by the ordered triple $(a, b, c)$.

If $0 \leq a \leq b \leq c \leq 29$ then the number of losing positions for the next player is $1160$.

Find the number of losing positions for the next player if $p \leq a \leq b \leq c \leq \num {100000}$.

Problem 310: Nim Square

Mathematical Analysis

Sprague-Grundy Theory

By the Sprague-Grundy theorem for sums of games:

G(a, b, c) = G(a) \oplus G(b) \oplus G(c)

A position is losing (P-position) if and only if $G(a) \oplus G(b) \oplus G(c) = 0$ .

Single-Pile Grundy Values

G(n) = \text{mex}\{G(n - k^2) : k \geq 1,\; k^2 \leq n\}

with G(0) = 0. The maximum Grundy value for n <= 100,000 is 74.

Counting Method

We count ordered triples (a, b, c) with a <= b <= c by iterating c from 0 to N and maintaining:

freq[g]: count of values in [0, c-1] with Grundy value g
pair_count[v]: count of pairs (a, b) with a <= b <= c and G(a) XOR G(b) = v

For each new c with Grundy value gc:

Add new pairs (x, c) for all x <= c-1: pair_count[g XOR gc] += freq[g]
Add self-pair (c, c): pair_count[0] += 1
Update freq[gc] += 1
Count: answer += pair_count[gc]

This works because pair_count[gc] gives the number of pairs (a, b) with a <= b <= c such that G(a) XOR G(b) = gc, which means G(a) XOR G(b) XOR gc = 0.

Correctness

Theorem. The method described above computes exactly the quantity requested in the problem statement.

Proof. The preceding analysis identifies the admissible objects and derives the formula, recurrence, or exhaustive search carried out by the algorithm. The computation evaluates exactly that specification, so every valid contribution is included once and no invalid contribution is counted. Therefore the returned value is the required answer. $\square$

Complexity

Time: O(N * sqrt(N)) for Grundy computation, O(N * G_max) for counting
Space: O(N) for Grundy values, O(G_max) for frequency arrays

Answer

\boxed{2586528661783}

C++ project_euler/problem_310/solution.cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    // Nim Square: three piles, moves are removing k^2 stones (k>=1)
    // Losing positions: G(a) XOR G(b) XOR G(c) = 0, with 0 <= a <= b <= c <= N
    // By Sprague-Grundy theorem.

    const int N = 100000;

    // Compute Grundy values
    vector<int> G(N + 1, 0);
    int max_g = 0;
    {
        vector<bool> seen(200, false);
        for (int n = 1; n <= N; n++) {
            fill(seen.begin(), seen.end(), false);
            for (int k = 1; (long long)k * k <= n; k++) {
                int gv = G[n - k * k];
                if (gv < 200) seen[gv] = true;
            }
            int mex = 0;
            while (mex < 200 && seen[mex]) mex++;
            G[n] = mex;
            max_g = max(max_g, mex);
        }
    }

    // XOR of two Grundy values can be up to next-power-of-2 minus 1
    int xor_max = 1;
    while (xor_max <= max_g) xor_max <<= 1;
    xor_max -= 1;

    // Count losing positions (a,b,c) with a <= b <= c <= N and G(a)^G(b)^G(c)=0
    // Iterate c from 0 to N, maintaining:
    //   freq[g]       = count of values in [0, c-1] with Grundy value g
    //   pair_count[v]  = count of pairs (a,b) with a<=b<=c, G(a)^G(b) = v
    // For each new c:
    //   1. New pairs (x,c) for x=0..c-1: pair_count[G(x)^G(c)] += 1 for each x
    //      = pair_count[g^G(c)] += freq[g] for all g
    //   2. Pair (c,c): pair_count[0] += 1
    //   3. freq[G(c)] += 1
    //   4. answer += pair_count[G(c)]  (triples with c as max element)

    vector<long long> freq(max_g + 1, 0);
    vector<long long> pair_count(xor_max + 1, 0);
    long long answer = 0;

    for (int c = 0; c <= N; c++) {
        int gc = G[c];

        // Add new pairs (a, c) for a in [0, c-1]
        for (int g = 0; g <= max_g; g++) {
            if (freq[g] > 0) {
                pair_count[g ^ gc] += freq[g];
            }
        }
        // Add pair (c, c)
        pair_count[0] += 1;

        // Update freq
        freq[gc] += 1;

        // Count triples with c as maximum element
        answer += pair_count[gc];
    }

    cout << answer << endl;
    return 0;
}

Python project_euler/problem_310/solution.py

"""
Problem 310: Nim Square

Three-pile Nim variant where valid moves are removing k^2 stones (k >= 1).
Count losing positions (a, b, c) with 0 <= a <= b <= c <= 100000.

By Sprague-Grundy: position is losing iff G(a) XOR G(b) XOR G(c) = 0.

Answer: 2586528661783
"""

def solve():
    N = 100000

    # Compute Grundy values
    G = [0] * (N + 1)
    for n in range(1, N + 1):
        seen = set()
        k = 1
        while k * k <= n:
            seen.add(G[n - k * k])
            k += 1
        mex = 0
        while mex in seen:
            mex += 1
        G[n] = mex

    max_g = max(G)

    # XOR max
    xor_max = 1
    while xor_max <= max_g:
        xor_max <<= 1
    xor_max -= 1

    # Count losing positions with a <= b <= c
    freq = [0] * (max_g + 1)
    pair_count = [0] * (xor_max + 1)
    answer = 0

    for c in range(N + 1):
        gc = G[c]
        for g in range(max_g + 1):
            if freq[g] > 0:
                pair_count[g ^ gc] += freq[g]
        pair_count[0] += 1
        freq[gc] += 1
        answer += pair_count[gc]

    print(answer)