Fabian Arevalo

Research note · Combinatorial game theory

The Bit Deletion game, solved

A two-term closed form for the Sprague–Grundy function settles both conjectures of OEIS A398916, gives the misère solution, and counts the positions of each value exactly.
September 3, 2026 · produced in a Claude Code research session (AI-assisted, disclosed) · code, data & certificate in the companion repository.

Start here: no maths required

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.

n 37
The rule, and a check that it is right, both running live in your browser. The top row is n in binary. After the leading one, each run of noughts is bracketed and labelled with its length and whether that length is odd or even. Count the odd-length runs before the first even-length one: call that count t. The value is then 2 if t is odd, plus 1 more if the number of digits is odd. Underneath, the same value is recomputed the slow honest way, by building the whole game tree from the definition and taking the least value not appearing among the options, and the two are compared. They agree for every n below 65,536, which the page checks on load rather than asserting: the count of disagreements is printed in the readout.

What this note adds

The sequence entry recorded two guesses from five million values of data. This note proves them, and rather more, from a three-line induction.

  1. An exact formula for the value of every position. Count the binary digits; that parity gives you 0 or 1. Then read the runs of noughts from the left and count how many odd-length ones you get through before the first even-length one; if that count is odd, add 2. That is the value, for every one of the infinitely many positions. It is proved, not observed.
  2. Both catalogued conjectures, settled. The value never exceeds 3, because the formula only ever adds 0 or 1 to 0 or 2. Multiplying by four sticks two noughts on the end, which changes neither the digit count’s parity nor any run’s parity, so the value cannot move. The entry had checked these to five million and one million respectively.
  3. Exactly how many positions have each value. Among the numbers with a given count of binary digits, exactly one quarter have a high value (2 or 3) and three quarters a low one (0 or 1), at every length from 3 digits upward. The number of losing positions below four to the power k is exactly 22k−1 − 1: seven below 16, thirty-one below 64, a hundred and twenty-seven below 256.
  4. The reverse game too. Play it so that taking the last one loses instead of wins, and the losing positions become exactly the positions whose ordinary value is 1. That is not a general fact about games; it happens to be true here and is proved.
  5. An honest note on what was already known. Who wins, as opposed to the value, is not new: this is Project Euler problem 961 in decimal clothing, and solvers there worked out the winning rule in 2025. That is marked as a rediscovery wherever it appears. The values themselves, the bound, the times-four invariance and the reverse game are what this note contributes.

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.

AbstractSummary of results

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.

Section 1The game and notation

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:

u = 0z1 1 0z2 1 ⋯ 1 0zm+1,   m = number of ones in u,   zi ≥ 0

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

t(u) = max{ t ≥ 0 : z1, …, zt are all odd },   h(u) = t(u) mod 2,   P(u) = (|u| + 1) mod 2 = L mod 2

Two facts are used constantly: h(0z) = [z odd], and for m ≥ 1, with u = 0z11v,

h(u) = [z1 odd] · (1 − h(v))(1)

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.

Section 2The Grundy function

Theorem 1 · PROVED

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.

Lemma D · the deletion lemmas · PROVED

Let u contain at least one 1, u = 0z11v, and write b1 = z1 mod 2.

  • (D1) If b1 = 1, some deletion ui has h(ui) = 0.
  • (D2) If b1 = 0 and h(v) = 1, some deletion ui has h(ui) = 0.
  • (D3) If b1 = 1 and h(v) = 0, some deletion ui has h(ui) = 1.

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),

D ⊆ { 1 − P(u) + 2h(ui) } ⊆ { 1 − P(u), 3 − P(u) }

and J = P(v) + 2h(v) if m ≥ 1, while J = 0 if m = 0.

Case A: |u| even, that is P(u) = 1

Then D ⊆ {0, 2}, so the values 1 and 3 can only come from J, and the claimed value is 1 + 2h(u).

Case B: |u| odd, that is P(u) = 0

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. □

Shade by
Theorem 1 as a picture: the value is the sum of two independent bits, and the two views show them separately. Every cell is one position n from 0 to 255, in reading order, its Grundy value computed from the definition in your browser. Switch to L parity and you see the units bit of the value alone, a pattern of doubling horizontal bands, because the digit count only changes at powers of two. Switch to t parity and you see the twos bit alone. The first view is exactly the two of them added, which is the theorem: the two bits are computed by completely different rules and never interact. The cell for n = 0 is left blank, being the terminal position rather than a position of the game.

Section 3What follows

Corollary 1 · the two OEIS conjectures · PROVED

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.

Corollary 2 · outcome classes · PROVED · rediscovery, marked

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.

Corollary 3 · distribution of values · PROVED

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),

Aℓ = [ℓ odd] + Σz odd, z ≤ ℓ−1 Bℓ−1−z

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. □

Scale
Hover or tap a bar to read the exact counts at that bit-length.
Measurement, not model: the counts are read from the certificate file, and the three-to-one split of Corollary 3 is checked against them at every length. One bar per bit-length L from 1 to 32, from data_grundy_check_2e32.txt, the output of the exhaustive run over all 4.29 billion positions below 232. The four bands are the four Grundy values. Two things are visible at once and both are theorems: only two of the four values occur at any given length, alternating with the parity of L, and the high value takes exactly one quarter of the bar every time. In the proportion view every bar is identical from L = 3 up, which is the content of Corollary 3; the count view shows the same data on a log scale, where the four-fold growth per two steps is the visible feature.

Section 4Misère play

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.

Theorem 2 · PROVED

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. □

Section 5Other bases, and sums of games

Remark 3 · other bases · PROVED · reduction is rediscovery, marked

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.

Remark 4 · sums · PROVED

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.

Section 6Computational verification

CERTIFIED · n < 232

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:

checkwhat it exercisesrangeresult
grundy_check.cTheorems 1 and 2 against a from-definition recomputation, in C, multithreadedall n < 2320 mismatches, max value 3
grundy.pythe same, in an independent pure-Python implementation sharing no codeall n < 2200 mismatches
grundy.pythe induction step of Theorem 1 and Lemma D, string by stringevery u with |u| ≤ 18, 524,287 strings0 failures
grundy.pythe 34 terms published in A398916n ≤ 34reproduced exactly
variants.pyRemark 3, from the base-b definitionsbases 3, 4, 5, 100 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.

Section 7What is new here, and what is not

This section exists because the honest answer is mixed, and the mix is easy to blur.

Section 8Open questions

  1. Two deletions per move, or deleting a run. The same game where a move removes two digits, or a whole contiguous block of equal digits, has not been analysed. The block-parity invariant of Theorem 1 does not obviously survive either change: both break the fact that a (D)-move flips the length parity, which is the hinge the whole induction turns on.
  2. Partizan versions. If each player may delete only certain digit values, the game stops being impartial and the Sprague–Grundy theory no longer applies. Project Euler 963, “Removing Trits”, is of this type.
  3. Does the value have a meaning? The formula computes a value from two parity counts that have nothing to do with each other. It would be more satisfying to exhibit the game as a sum or a quotient of two simpler games, one contributing the units bit and one the twos bit, rather than to verify the split by induction after the fact.