Research note · Combinatorial game theory
Write a number in binary, so it becomes a row of noughts and ones. Two players take turns. A move is to rub out any single digit; the rest close up the gap, and if that leaves noughts at the front you drop them. Whoever rubs out the last remaining one wins.
That is the whole game. It takes ten seconds to explain and you can play it on the back of an envelope. The question is the usual one: given the starting number, who wins, and how?
For games like this there is a standard answer that is stronger than just naming the winner. Every position gets a whole number, its value, and the position is a loss for whoever has to move exactly when that value is zero. The values also tell you how to play several of these games side by side at once. Somebody computed the values for this game up to five million and noticed two things they could not explain: the value never seemed to exceed 3, and multiplying the starting number by four never seemed to change it. Those two observations went into the sequence catalogue as open conjectures.
Both turn out to be true, and for a reason you can carry out by hand in a few seconds. Try it on the figure below.
The sequence entry recorded two guesses from five million values of data. This note proves them, and rather more, from a three-line induction.
Everything below is the technical version: the block notation, the three deletion lemmas the induction runs on, the proofs, the counts, and the exhaustive machine check to 4.29 billion positions.
The Bit Deletion game (OEIS A398916, Do Thanh Nhan, 14 Aug 2026) is played on a positive integer written in binary: a move deletes one binary digit, leading zeros are then discarded, and the player who removes the last nonzero digit wins. We determine the Sprague–Grundy function completely. Writing the binary expansion as 1 0z1 1 0z2 1 ⋯ 1 0zm+1 (blocks may be empty), let L be the number of binary digits and t the number of initial blocks of odd length. Then G(n) = (L mod 2) + 2·[t odd]. This proves both conjectures recorded in A398916 (G(n) ≤ 3 for all n, and G(4n) = G(n)), gives the exact distribution of values (exactly one quarter of the L-bit numbers, L ≥ 3, have value 2 or 3), and settles the misère form: the misère P-positions are exactly the positions of normal Grundy value 1. The outcome classes alone (Corollary 2) are folklore among solvers of Project Euler Problem 961, the decimal form of the same game, and are marked as a rediscovery throughout; the Grundy values, the bound, the 4n invariance and the misère analysis are, as far as a same-day literature search could determine, new. Both theorems are additionally verified by exhaustive computation from the definition for all n < 232 = 4,294,967,296.
Positions. Nonnegative integers. From n ≥ 1 with binary expansion d1d2⋯dL (d1 = 1) a move deletes one digit di; the remaining L − 1 digits, read as a binary numeral with leading zeros discarded, form the new position. The position 0 has no moves. Normal play: the player who moves to 0, that is, who removes the last nonzero digit, wins. G(n) is the Sprague–Grundy value, G(0) = 0 and G(n) = mex{G(n′) : n′ an option of n}.
Block decomposition. For n ≥ 1 write bin(n) = 1u with u ∈ {0,1}L−1, and decompose u by its ones:
Empty blocks are allowed: z1 is the number of zeros before the first one of u, zm+1 the number after the last one; if m = 0 then u = 0z1. Define
Two facts are used constantly: h(0z) = [z odd], and for m ≥ 1, with u = 0z11v,
If z1 is even then t(u) = 0; if z1 is odd then t(u) = 1 + t(v).
Options in this notation. From n = 1u there are two kinds:
The whole proof lives in the gap between these two: a (D)-move always flips the length parity, and a (J)-move preserves it exactly when the block it jumps over is odd. That is why the parities of the leading blocks are the thing that matters.
For every n ≥ 1, with u, L, t as above, G(n) = (L mod 2) + 2·[t(u) odd] = P(u) + 2h(u). In particular G(n) ∈ {0,1,2,3}, G(n) ≡ L (mod 2), and the value is at least 2 exactly when the initial run of odd-length zero-blocks has odd length.
The proof is an induction on n, equivalently on |u|, and it rests on three statements about single deletions that involve only h.
Let u contain at least one 1, u = 0z11v, and write b1 = z1 mod 2.
Moreover, if u = 0z with z odd, the deletion 0z−1 has h = 0.
Proof. (D1): z1 is odd, hence at least 1; deleting one zero of the first block makes z1 even, so t(ui) = 0 and h(ui) = 0.
(D2): h(v) = 1 forces the first block of v to have odd length z2 ≥ 1, by (1) applied to v, or by h(0z2) = [z2 odd] if v has no one. Deleting one zero of that block leaves the first block of u untouched, so t(ui) = 0 because z1 is even, and h(ui) = 0.
(D3): Let z2 be the length of the first block of v, so v = 0z2 or v = 0z21w. By (1), h(ui) = 1 − h(vi) for every deletion that happens inside v, so it suffices to find a deletion vi of v with h(vi) = 0, or else to use the deletion of the first one of u. Three cases:
The final statement is h(0z−1) = [z − 1 odd] = 0. □
Proof of Theorem 1. Induction on |u|. Assume the formula for every position with a shorter u, and G(0) = 0. Let D be the set of values of the (D)-options and J the value of the (J)-option. By induction and P(ui) = 1 − P(u),
and J = P(v) + 2h(v) if m ≥ 1, while J = 0 if m = 0.
Then D ⊆ {0, 2}, so the values 1 and 3 can only come from J, and the claimed value is 1 + 2h(u).
Then D ⊆ {1, 3}, so the value 0 can only come from J, the value 2 never occurs as an option value, and the claimed value is 2h(u).
All cases agree with the formula, completing the induction. □
G(n) ≤ 3 for all n, and G(4n) = G(n) for all n ≥ 1.
Proof. The first is immediate from the formula, whose two terms lie in {0,1} and {0,2}. For the second, multiplying by 4 appends 00 to the binary expansion: L increases by 2 and the last block zm+1 increases by 2, which changes neither L mod 2 nor any block parity, hence not t. □
Also G(2n) ≢ G(n) (mod 2) for every n ≥ 1, since the bit-length changes by one, so the sequence G(n), G(2n), G(4n), … has period exactly 2. The “period dividing 2” that the OEIS entry derives from its second conjecture is never period 1.
n ≥ 1 is a P-position, meaning the previous player wins, if and only if L is even and t(u) is even. Equivalently, with u = 0z11v: an even-length position is a P-position iff z1 is even, or z1 is odd and the position 1v is an N-position; every odd-length position is an N-position.
Provenance. This corollary is not new. Project Euler Problem 961, “Removing Digits” (21 Sep 2025, linked from the OEIS entry), is the decimal form of the game, and public solution write-ups state exactly this P/N rule together with the base reduction of Remark 3. Those write-ups are unrefereed and are cited as secondary; the Project Euler forum itself is login-walled and was not read. The corollary is recorded here because it falls out of Theorem 1 in one line, and because the Grundy values, which the P/N rule does not determine, are what the OEIS conjectures are actually about.
For L ≥ 3, exactly 2L−3 of the 2L−1 numbers with L binary digits have Grundy value in {2,3}; the other 3·2L−3 have value in {0,1}. Hence, for k ≥ 1, the number of P-positions below 4k is 22k−1 − 1.
Proof. Let Aℓ be the number of u ∈ {0,1}ℓ with h(u) = 1, and Bℓ = 2ℓ − Aℓ. Classifying u by its first block (u = 0ℓ, or u = 0z1v with |v| = ℓ − 1 − z) and using (1),
Subtracting the same identity for ℓ − 2, where the indicators agree and the sums differ by the single term z = 1, gives Aℓ − Aℓ−2 = Bℓ−2 for all ℓ ≥ 2, with A0 = 0 and A1 = 1; that is Aℓ = Aℓ−2 + 2ℓ−2 − Aℓ−2 = 2ℓ−2. The L-bit numbers correspond to ℓ = L − 1. By Theorem 1 the P-positions are the L-bit numbers with L even and h = 0: one for L = 2, namely n = 3, and 3·2L−3 for each even L ≥ 4; summing over L = 2, 4, …, 2k gives 1 + 6(1 + 4 + ⋯ + 4k−2) = 22k−1 − 1. □
In misère play the player who removes the last nonzero digit loses; the position 0 is then a win for the player to move, the opponent having just lost. Misère versions of impartial games are usually far harder than their normal forms and rarely have a clean description in terms of the normal-play values. This one does.
In misère play, n ≥ 1 is a P-position if and only if G(n) = 1, that is iff L is odd and t(u) is even. For k ≥ 0 there are exactly 4k misère P-positions below 22k+1.
Proof. Induction on n, the statement being that “misère P” coincides with “G = 1” on all options. A position is misère-P iff none of its options is misère-P, that is, by induction, iff no option has Grundy value 1. If G(n) = 1 then 1 is not an option value, so n is misère-P. If G(n) ≥ 2 then 1 is an option value, so n is misère-N. If G(n) = 0 we must exhibit an option of value 1: by Theorem 1 this is Case B2, or Case B3 with h(v) = 1. In B2, J ∈ {1,3}; if J = 1 we are done, and if J = 3 then h(v) = 1 and (D2) gives a deletion with h(ui) = 0, whose value is 1 − P(u) + 0 = 1. In B3, (D1) gives a deletion with h(ui) = 0, again of value 1. Finally n = 0 is misère-N and G(0) = 0 ≠ 1, so the base case is consistent. The count follows from Corollary 3: n = 1, plus 3·2L−3 positions for each odd L with 3 ≤ L ≤ 2k+1, that is 1 + (4k − 1) = 4k. □
Play the same game on base-b digits, b ≥ 2: delete one digit, discard leading zeros, last nonzero digit wins. Only the pattern of zero versus nonzero digits matters. The map μ replacing every nonzero digit by 1 sends the options of n exactly onto the options of μ(n), so Gb(n) = G(μ(n)) by induction, and Theorems 1 and 2 apply verbatim with “zero-blocks” read in base b.
This reduction is also part of the Project Euler 961 folklore and is cited as secondary. It was verified here directly from the base-b definitions for bases 3, 4, 5 and 10, up to 313, 410, 59 and 106 respectively (variants.py: 0 mismatches, maximum value 3 in each base). The practical consequence is that Project Euler 961, which is the decimal game, has the same answer structure as the binary one, and that the whole analysis is really about runs of zeros rather than about binary.
By the Sprague–Grundy theorem, a disjunctive sum of Bit Deletion positions n1, …, nr is a P-position iff G(n1) ⊕ ⋯ ⊕ G(nr) = 0, with each G(nj) ∈ {0,1,2,3} read off from Theorem 1 in time linear in the number of digits.
For example, the two-component game 5 + 5 has values 3 ⊕ 3 = 0 and is a P-position, while 5 + 2 has 3 ⊕ 2 = 1 and is not. This is the payoff of computing the values rather than only the winner: the outcome rule of Corollary 2 says nothing at all about sums, and no amount of it would.
grundy_check.c recomputes, from the definition, the Grundy value and the misère outcome of every n < 232 = 4,294,967,296, level by bit-length, and compares both with the closed forms. Result: 0 mismatches for Theorem 1, 0 mismatches for Theorem 2, and no value exceeding 3; at every bit-length L ≥ 3 the count of values in {2,3} is exactly 2L−3, as Corollary 3 requires. Runtime 177 s on 4 threads, 4 GB RAM; output committed as data_grundy_check_2e32.txt.
The level-by-level structure is what makes the check cheap: all options of an L-bit number have fewer bits, so each bit-length can be computed from the ones below it and the levels are embarrassingly parallel. The three independent checks, deliberately overlapping as little as possible, are:
| check | what it exercises | range | result |
|---|---|---|---|
| grundy_check.c | Theorems 1 and 2 against a from-definition recomputation, in C, multithreaded | all n < 232 | 0 mismatches, max value 3 |
| grundy.py | the same, in an independent pure-Python implementation sharing no code | all n < 220 | 0 mismatches |
| grundy.py | the induction step of Theorem 1 and Lemma D, string by string | every u with |u| ≤ 18, 524,287 strings | 0 failures |
| grundy.py | the 34 terms published in A398916 | n ≤ 34 | reproduced exactly |
| variants.py | Remark 3, from the base-b definitions | bases 3, 4, 5, 10 | 0 mismatches, max value 3 |
For comparison, the OEIS entry had checked its first conjecture to 5 × 106 and its second to 106. The extension to 232 is not what settles them, though: the theorem does, and the computation is a check on the proof rather than a substitute for it. The distinction matters here more than usual, because a bound like “never exceeds 3” is exactly the kind of statement that a finite check can support forever without ever establishing.
This section exists because the honest answer is mixed, and the mix is easy to blur.