Detailed mathematical approach

Problem Summary

Start from a positive integer \(n\). One move removes a single decimal digit, keeps the remaining digits in their original order, and then discards any leading zeros that appear. If every digit has been removed, the next state is \(0\), and the player to move loses. The goal is to count how many starting values below \(10^{18}\) are winning positions for the first player.

The key simplification is that the exact nonzero digits never matter. Only the pattern of zero and nonzero positions matters, so the whole game can be compressed to a short binary mask and then lifted back to decimal numbers by a simple weight.

Mathematical Approach

Encode a number by its zero pattern

For an \(\ell\)-digit decimal number \(d_1d_2\cdots d_\ell\) with \(d_1\neq 0\), define a binary mask \(b_1b_2\cdots b_\ell\) by

$b_i=\begin{cases}1,&d_i\neq 0,\\0,&d_i=0.\end{cases}$

Two numbers with the same mask have the same game tree. Deleting the \(i\)-th decimal digit deletes the \(i\)-th bit, and removing leading zeros depends only on where the first remaining \(1\) sits. So every state can be represented by a canonical binary string that is either empty or begins with \(1\).

If a mask contains \(t\) ones, it represents exactly \(9^t\) different decimal numbers, because each active position may hold any digit from \(1\) to \(9\), while the zero positions are forced.

The recursive game state

Let \(\mathcal{W}(m)\) denote whether a canonical mask \(m\) is winning. Under normal play,

$\mathcal{W}(m)=1 \iff \exists\, m'\,(m\to m' \land \mathcal{W}(m')=0).$

and the empty mask is losing. This is exactly the recurrence evaluated by the implementations.

Writing a nonempty canonical mask as \(1\,0^r\,u\), where \(r\ge 0\) counts the zeros immediately after the leading \(1\) and \(u\) is either empty or begins with \(1\), is the right way to read the recursion: deleting the first bit jumps directly to the suffix \(u\), while deleting any other bit leaves the leading \(1\) in place.

Odd lengths versus even lengths

A short induction on the mask length gives two structural facts that explain why the search is so regular.

Every odd-length canonical mask is winning. For even lengths, the situation is much tighter: deleting any non-leading bit keeps the first bit equal to \(1\), so the child has odd length and is therefore winning. That means an even-length mask can only win by deleting its first bit.

Hence an even mask \(1\,0^r\,u\) is winning exactly when deleting the leading digit exposes a losing state, which is equivalent to saying that \(r\) is odd and \(u\) is either empty or itself a losing mask. The parity of the first zero run is the decisive invariant.

Worked example

The mask \(1100\) is losing. Deleting one of the first two bits produces \(100\), and deleting one of the last two bits produces \(110\). Both children have odd length, so both are winning.

Now consider \(101100\). If the first bit is deleted, the raw result is \(01100\), which canonicalizes to \(1100\), a losing state. Every other deletion leaves a 5-bit state, and every 5-bit state is winning. So \(101100\) is winning. Since it has three ones, it corresponds to \(9^3=729\) actual six-digit numbers.

Counting winning numbers by length

Let \(A_n\) be the weighted number of winning masks of length \(n\), and \(B_n\) the weighted number of losing masks of length \(n\). Set \(B_0=1\) for the empty mask. The total weight of all \(n\)-digit masks is \(9\cdot 10^{n-1}\).

Because every odd-length mask is winning,

$A_{2m+1}=9\cdot 10^{2m}.$

For even length \(2m\), a winning mask must have the form \(1\,0^{2k+1}\,u\), where \(u\) is empty or a losing even-length mask. The prefix contributes only the leading nonzero digit, so

$A_{2m}=9\sum_{j=0}^{m-1} B_{2j}, \qquad B_{2m}=9\cdot 10^{2m-1}-A_{2m}.$

Eliminating \(B_{2m}\) gives a one-step recurrence for the even lengths:

$A_2=9,\qquad A_{2m+2}=81\cdot 10^{2m-1}-8A_{2m}\quad (m\ge 1).$

This solves to

$A_{2m}=\frac{15\cdot 100^{m-1}+3(-8)^{m-1}}{2}.$

The required answer is the cumulative total

$W(10^E)=\sum_{n=1}^{E} A_n.$

For even exponents, the sum collapses neatly to

$W(10^{2m})=\frac{100^m-(-8)^m}{6}.$

The small checks follow immediately: \(W(10^2)=18\) and \(W(10^4)=1656\).

How the Code Works

The C++, Python, and Java implementations solve the game directly on canonical masks of length at most \(18\). For each length \(\ell\), they enumerate every mask whose highest bit is \(1\), so each possible zero/nonzero pattern is considered exactly once.

Each state is evaluated by memoized recursion. The implementation tries every deletion position, builds the next mask with bit operations, shortens the apparent length while leading zeros remain, and stops as soon as it finds one losing child. Once a mask has been classified, that result is reused everywhere else.

After the win/loss table is known, the final accumulation is simple. A winning mask with \(t\) ones represents \(9^t\) decimal numbers, so the implementation adds the corresponding power of \(9\) for every winning mask of every length from \(1\) through \(18\).

Complexity Analysis

There are \(2^{\ell-1}\) canonical masks of length \(\ell\), so the total number of states up to length \(E\) is

$\sum_{\ell=1}^{E} 2^{\ell-1}=O(2^E).$

Each state tests up to \(\ell\) deletions, and each transition performs a short normalization step to remove leading zeros. A conservative upper bound for the direct recursive implementation is therefore \(O(E^2 2^E)\), with \(O(2^E)\) memory for the memo table.

For the actual target \(E=18\), this is tiny. The regular formulas above explain the structure of the answer, but the brute-force mask recursion is already more than fast enough.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=961
2. Impartial game: Wikipedia - Impartial game
3. Combinatorial game theory: Wikipedia - Combinatorial game theory
4. Dynamic programming: Wikipedia - Dynamic programming
5. Leading zero: Wikipedia - Leading zero
6. Positional notation: Wikipedia - Positional notation