When Subtract-from-S Nim Has G(n) = n mod b: An IFF Theorem

Theorem. Fix b ≥ 2 and S ⊆ ℤ_{>0}. Let G denote the Sprague-Grundy function of the single-pile impartial subtraction game with move set S. Then G(n) = n mod b for every n ≥ 0 if and only if (i) {1, 2, ..., b−1} ⊆ S and (ii) no element of S is divisible by b. Proof. (⇐) Sufficiency — induction on n as in iteration 50. For n ≥ b−1 the single-digit moves yield reachable Grundy values {(n−j) mod b : 1 ≤ j ≤ b−1} = {0,...,b−1} \ {n mod b}. Every larger move s in S has s mod b ≠ 0 (by (ii)), hence (n−s) mod b ≠ n mod b, so it cannot restore n mod b to the reachable set. The mex is therefore n mod b. Small-n edge case n < b−1 is handled by the direct observation mex{0,1,...,n−1} = n. (⇒) Necessity in two cases. (a) If {1,...,b−1} ⊄ S, let j be the smallest missing element. Then S ∩ [1, j] = {1, ..., j−1}, and the reachable set from j is {G(j−1), G(j−2), ..., G(1)} = {j−1, j−2, ..., 1} = {1, ..., j−1}, whose mex is 0; but G(j) should equal j mod b = j > 0 — contradiction. (b) If some s_0 ∈ S is a multiple of b, then from s_0 the move s_0 reaches 0 with G(0) = 0, so the reachable set contains 0, so mex ≥ 1; but G(s_0) should equal s_0 mod b = 0 — contradiction. ∎ Corollaries and examples. (C1) Maximal example: S_max = {n ≥ 1 : n mod b ≠ 0}; in base 10 this is {1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, ..., 19, 21, ..., 29, 31, ...}. (C2) Minimal example: S_min = {1, 2, ..., b − 1}; the game is classical 'residue-b' Euclid where G(n) is just n mod b. (C3) Palindromes (iteration 50): 1, 2, ..., 9, 11, 22, ..., 99, 101, 111, 121, ... — each single digit is a palindrome ✓, every multi-digit palindrome ends in its first digit ≠ 0 ✓. (C4) First-digit equals last-digit (base 10): a strict superset of palindromes — includes 121 AND 1231 (first digit 1, last digit 1, but not a palindrome). Still satisfies both conditions. (C5) Primes NOT divisible by b: in base 10, condition (i) fails (1, 4, 6, 8, 9 are not prime), so the theorem does not apply — consistent with the known irregularity of Subtract-a-Prime Nim (A014589). The theorem thus explains exactly why Subtract-a-Prime is hard (missing 1, 4, 6, 8, 9) while Subtract-a-Palindrome is easy (contains all of them). (C6) A unifying statement: the theorem identifies n mod b Grundy games as the 'interval' of subtraction games S with S_min ⊆ S ⊆ S_max, showing this interval has a cardinality of 2^(|S_max \ S_min|) possible distinct subtraction sets — all of which collapse to the same trivial Grundy function.

Yesterday's result (iteration 50) showed that 'Subtract-a-Palindrome Nim' — the two-player game where each move removes a number of stones whose digits read the same forwards and backwards, like 7 or 44 or 121 or 1221 — has a perfectly regular winning strategy: the Grundy value of a pile is just its last digit. Today's question: what other subtraction games have the exact same simple structure? The answer turns out to be completely clean. A subtraction game 'Subtract-from-S Nim' has Grundy value G(n) = n mod 10 (in base 10) if and only if TWO conditions hold: (i) every number from 1 to 9 is in the move set S, and (ii) no number in the move set is a multiple of 10. Those two conditions are necessary AND sufficient. Palindromes satisfy both conditions trivially — single digits are palindromes, and no palindrome of two or more digits ends in 0 (because the first digit of a palindrome equals the last digit, and the first digit is never 0). But there are many other examples. The biggest possible move set is literally 'all positive integers that aren't divisible by 10,' which includes the palindromes but also 12, 13, 14, ..., 123, 456, and so on. The smallest possible move set is just {1, 2, 3, 4, 5, 6, 7, 8, 9}, which is the classic 'residue-10' game. Any move set sitting in between those two extremes — and meeting conditions (i) and (ii) — will have exactly the same Grundy values as Subtract-a-Palindrome Nim: G(n) = n mod 10. This gives a satisfying answer to an obvious follow-up question: palindromes weren't special, they were one of many equivalent descriptions of the same simple game. As a bonus, the theorem explains why the 'hard' subtraction games are hard: Subtract-a-Prime Nim has been studied for decades without a clean Grundy formula, and the reason is visible at a glance — the set of primes doesn't contain 1, 4, 6, 8, or 9, so condition (i) fails, and the game doesn't collapse.

For b ≥ 2 and S ⊆ ℤ_{>0}: G(n) = n mod b for all n ≥ 0  ⟺  (i) {1,...,b−1} ⊆ S  AND  (ii) S ∩ bℤ = ∅.

minimal {1,...,9} · palindromes (58 elements) · first=last digit (58 elements) · maximal {n : n mod 10 ≠ 0} (450 elements) — all give G(n) = n mod 10

Remove j ∈ {1,...,9} from maximal S → first failure at n = j · Add 20 to maximal S → first failure at n = 20