Number · a reach · combinatorial game theory

One Word Apart

Two coin games sit one word apart. In one, your bite must share no factor with the pile. In the other, it must share one. Flip that word and a game won by the least prime factor of the pile turns into one whose values are, give or take one, an integer sequence defined in 2016 with no game in it at all: label the integers as early as you can so that equal labels only ever sit at coprime positions.

Both are impartial games with normal play: players alternate, and whoever takes the last token wins. The tool for such games is the Sprague–Grundy value G(n) of a pile: a single number that says how the pile behaves when several are played at once. Two heaps together are a first-player loss exactly when G(a) XOR G(b) = 0. Every value below is recomputed in your browser, from the definition, as you watch.

Play them

Set up a few piles and play a perfect engine. It moves to leave the Grundy XOR at zero whenever it can, which is optimal play. Notice: in Common-factor Nim you can always empty a single pile in one bite, so with one pile it is trivial. The game only has teeth with several piles, and there the Grundy value is what you are really fighting over.

The Grundy spectrum

Here is G(n) for every pile from 0 up, its colour keyed to the value, each number computed live by the mex rule (the smallest value not reachable in one legal move). Switch games and the whole character changes.

Coprime Nim is the least prime factor

Play with the spectrum on coprime and the pattern is stark. Every even pile is a zero. Every odd pile lights up with a value that is nothing other than the index of its smallest prime factor: 3 and 9 and 15 all show 2 (their least prime is the 2nd prime, 3); 5, 25, 35 show 3; 7, 49 show 4. A prime pile shows its own rank among the primes. The winning theory of the entire game is written in the primes.

Why. From an even pile every legal bite is odd (an even bite shares the factor 2), so it lands on an odd pile; and from an odd pile the bite d=1 is always legal (1 is coprime to everything) and lands on an even pile. So evens and odds strictly alternate under the moves, which forces the evens to be the losing positions, G=0. Now take an odd pile n whose least prime is the k-th prime. The value k is the one thing the mex cannot skip past and the one thing it cannot reach: taking d=1 lands on an even pile (value 0) and d=n−1 lands on the pile of 1 (value 1), the lower values fill in likewise, yet no legal bite can reach a pile whose own least prime is also p, because two piles sharing the prime p differ by a multiple of p, and the coprime rule forbids exactly that bite. So k is missing while everything below it is present, and the mex is k. That the lower values are always present is the step we verify exhaustively (to n=20000) rather than argue in full here. The one seam is n=1: it has no prime factor, and sits at G=1. Those odd values are OEIS A055396, so this is not a new sequence, and the law is not new either: the same game is Codeforces problem 2004E, “Not a Nim Problem” (2024), whose known solution is exactly this law, with a proof of the step verified here. What the page adds is the chance to watch a Nim variant compute the least prime factor.

Flip the word, and it looks wild

Now switch the spectrum to common-factor. The even piles form a clean staircase, where a pile of 2k is worth exactly k. But the odd piles scatter. Odd primes drop to 1, odd prime-squares to 2, and the rest jump around. It looks lawless. It is a sequence someone else wrote down first, for a reason that has nothing to do with games.

The full Grundy sequence of Common-factor Nim is in the OEIS under another name. For every n ≥ 2, G(n) equals A370822(n) (Neal Gersh Tolunsky, 2024) and equals 1 + A279119(n) (Rémy Sigrist, 2016): the earliest labelling of the integers in which equal labels sit only at coprime indices. The reason takes two lines. From a pile n ≥ 2 a move reaches exactly the piles m < n with gcd(m, n) > 1; that always includes 0 (take the whole pile), and never the pile of 1, since gcd(1, n) = 1. So the mex is A279119's defining rule shifted up by one. A search on 2026-07-19 missed it because the string it searched began with G(0), G(1) = 0, 0, which A370822 does not have. Here is the odd-pile subsequence, recomputed live: it is A370822's odd bisection.

The check

The honest lines: proved results are argued in full above; checked results are verified exhaustively to n = 20000 but not proved here; in OEIS marks what was published before this page, which it failed to find at first (see the correction below). The machinery (Sprague–Grundy theory) is classical (Sprague 1935, Grundy 1939; Berlekamp, Conway & Guy, Winning Ways, 1982). The computed sequences were deposited on Zenodo (10.5281/zenodo.21943905, from oversight/oeis/gcd-nim/); that deposit's claim that Common-factor Nim's sequence is new is superseded by the correction below, and the record awaits a new version.