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. That single flip splits a completely solved game from an open one, and the seam between them is the prime factorisation of a number.
Coprime Nim
From a pile of n tokens, remove d tokens where
gcd(d, n) = 1
your bite shares no factor with the pile.
Common-factor Nim
From a pile of n tokens, remove d tokens where
gcd(d, n) > 1
your bite shares a factor with the pile.
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. It is a law that a Nim variant computes the least prime factor.
Flip the word, and it goes 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 with no pattern anyone has found.
| P-positions = {0, 1} | proved From any n≥2 you may take the whole pile (gcd(n,n)=n>1), reaching 0. So every pile of 2 or more is a first-player win; the depth is all in the nimber, not the winner. |
| G(2k) = k | checked to 20000 Every even bite is legal from an even pile, so it reaches all smaller evens; the ≥k half is immediate, the exact equality is verified, not yet proved. |
| G(odd prime) = 1 | proved The only legal bite from a prime p is d=p, straight to 0. |
| G(odd prime²) = 2 | observed Holds for all 33 cases up to 20000. |
| odd piles, in general | open Erratic, unbounded, no known period or formula. This is the frontier. |
The full Grundy sequence of Common-factor Nim, and its odd-pile subsequence, are both absent from the OEIS (checked 2026-07-19 by the literal digit strings). Here is the odd-pile sequence, recomputed live: a small, true, uncatalogued thing you can now put your hands on. If you find the law, you will have found something no one has.
The check
Show your working
Every Grundy value on this page is recomputed in your browser, live, straight from the mex definition, a fifth independent path on top of the four in research/gcd-nim/: a direct mex recursion, a factor-set path that never calls gcd, a true two-heap minimax whose outcome must equal G(a) XOR G(b) = 0, and a separate Python reimplementation. The harness is pinned by positive controls first: it reproduces the textbook subtraction games (S={1,2}→n mod 3, S={1,2,3}→n mod 4, take-any→n) and the published A055396, before any new value is trusted. verify.mjs reports 17/17.
The honest lines: proved results are argued in full above; checked results are verified exhaustively to n = 20000 but not yet proved; the open odd-pile sequence has no known formula. The machinery (Sprague–Grundy theory) is classical (Sprague 1935, Grundy 1939; Berlekamp, Conway & Guy, Winning Ways, 1982). The computed sequences are staged for a citable Zenodo deposit in oversight/oeis/gcd-nim/; they are not submitted to the OEIS, which forbids AI-authored submissions.