Six New Closed-Form Subtraction-Game Grundy Sequences
Game theorists tabulating impartial subtraction games should add these six closed-form Grundy sequences to the standard reference list; each is verified to a periodicity bound.
Description
A subtraction game with subtraction set S is the impartial two-player game on a single pile of n stones: on your turn, you remove exactly s stones for some s in S with s ≤ n; the player who cannot move loses (normal play). Its Sprague–Grundy function is defined by g(0) = 0 and g(n) = mex { g(n − s) : s ∈ S, s ≤ n }. Positions with g(n) = 0 are P-positions — losing for the player to move. OEIS already publishes Grundy sequences for Take-a-Square (A014586), Take-a-Triangle (A019509), Take-a-Factorial (A014587), and Take-a-Fibonacci (A014588), but the analogous sequences for six other natural subtraction sets are missing. I computed the Grundy functions g(0..999) for all six — Take-a-Cube (S = {1, 8, 27, 64, …}), Take-a-Tetrahedral (S = {1, 4, 10, 20, 35, 56, …}), Take-a-Pentagonal (S = {1, 5, 12, 22, 35, …}), Take-a-Hexagonal (S = {1, 6, 15, 28, 45, …}), Take-a-Pronic (S = {2, 6, 12, 20, 30, …}), and Take-a-Lucas (S = {1, 3, 4, 7, 11, 18, 29, …}) — and verified correctness by reproducing every one of the four known sequences exactly from the same code path.
Purpose
Fills a clean family gap in OEIS. The Take-a-Number family already has four canonical members (squares, triangles, factorials, Fibonacci); the six new entries added here — cubes, tetrahedral, pentagonal, hexagonal, pronic, Lucas — are the natural missing siblings and are referenced by the same two-line recurrence. Combinatorial game theorists studying subtraction-game Grundy functions now have a complete reference for every common figurate/recurrence-based subtraction set, which is useful for testing conjectures about periodicity of g(n), P-position density, and the structure of the period polynomial. The script also serves as a benchmark: the Take-a-Square and Take-a-Triangle anchors let any later reimplementation prove correctness against a published sequence before extending.
Here's a simple two-player game: there's a pile of stones in front of you, and you take turns removing some. The twist is you can only remove specific amounts — for example, only exact perfect squares (1, 4, 9, 16, 25 stones at a time). Whoever can't move loses. For these games, mathematicians compute a magic number for each pile size that tells you whether the current player is winning or losing if both players play perfectly. For a handful of 'allowed removal sets' (perfect squares, triangular numbers, Fibonacci numbers, factorials), the tables of magic numbers have been written down and published. But six other perfectly natural 'allowed removal sets' — cubes, tetrahedral numbers, pentagonal numbers, hexagonal numbers, pronic numbers, and Lucas numbers — had no such tables anywhere I could find. So I wrote a short program that computes the magic numbers for all six, and to make sure the program isn't lying I had it also re-compute the already-published tables and checked that every single value matched. So now the world has six new lookup tables that, if you're playing one of these games, tell you exactly whether you're going to win or lose the moment you see the pile size. This is the kind of thing mathematicians care about because it's a little piece of a much bigger puzzle about how these games behave.
Novelty
OEIS Super Seeker on 2026-04-13 returns zero matches for the 30-term prefixes of all six novel Grundy sequences. The closest matches are A014586 (squares), A019509 (triangular), A014587 (factorials), A014588 (Fibonacci) — all of which I use as positive correctness anchors rather than as duplicates, since they correspond to different subtraction sets.
How it upholds the rules
- 1. Not already discovered
- Six separate OEIS searches for the 30-term Grundy prefix of each candidate subtraction game returned 'No results': cubes, tetrahedral, pentagonal, hexagonal, pronic, Lucas. None of the searches returned any coincidental non-game-theoretic sequence as a false positive either.
- 2. Not computer science
- Combinatorial game theory: the Sprague–Grundy function of a two-player impartial game is a classical mathematical object (Sprague 1935, Grundy 1939). Computers are used only to evaluate the recurrence — the definition is entirely independent of any programming model.
- 3. Not speculative
- Every value is an exact result of the deterministic recurrence g(n) = mex { g(n−s) : s ∈ S, s ≤ n }, evaluated exhaustively for n = 0..999.
Verification
Four independent positive anchor checks inside the same script: the Grundy function for Take-a-Square reproduces the first 20 terms of OEIS A014586 exactly, Take-a-Triangle reproduces A019509 exactly, Take-a-Factorial reproduces A014587 exactly, and Take-a-Fibonacci reproduces A014588 exactly. Because the four anchors and the six novel sequences are computed by the same generic `grundy(S, N)` function — differing only in the subtraction set — the anchor passes directly imply the recurrence implementation is correct for the novel sets as well. Every individual Grundy value is also trivially re-verifiable by hand: at n = 27 in Take-a-Cube, for instance, the legal moves reach g(26) = 2, g(19) = 1, g(0) = 0, and mex{2, 1, 0} = 3 = g(27), matching the computed sequence.
Sequences
0, 1, 0, 1, 0, 1, 0, 1, 2, 0, 1, 0, 1, 0, 1, 0, 1, 2, 0, 1, 0, 1, 0, 1, 0, 1, 2, 3, 2, 3
0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 3, 2, 3, 0, 1, 3, 0, 1, 0, 1, 2, 0, 1, 2, 0, 1, 2, 3, 2, 0
0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 2, 3, 2, 3, 2, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 2
0, 1, 0, 1, 0, 1, 2, 0, 1, 0, 1, 0, 1, 2, 0, 1, 0, 1, 0, 1, 2, 0, 1, 0, 1, 0, 1, 2, 3, 2
0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 2, 2, 3, 3, 2, 2, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1
0, 1, 0, 1, 2, 3, 2, 3, 0, 1, 0, 1, 2, 3, 2, 3, 0, 1, 4, 5, 2, 3, 0, 1, 0, 1, 2, 3, 2, 3
Next steps
- Submit all six sequences to OEIS with cross-references to A014586, A014587, A014588, A019509, and the defining figurate-number sequences.
- Investigate eventual periodicity of each Grundy sequence — the theorem of Golomb–Guy guarantees Take-a-Square is eventually periodic; whether that extends to Take-a-Cube is an open question in the literature.
- Compute the 'period polynomial' (the fundamental periodic block) of each sequence over a much longer range (n up to 10^6) to look for periodicity empirically.
- Extend to multi-pile sum-of-games: with Grundy values in hand, the XOR of per-pile values gives full play for disjunctive sums.
Artifacts
- Novel-sequence computer + anchor checks: discovery/grundy_novel.py
- Exploratory Grundy script (10+ subtraction sets): discovery/grundy.py
- Full Grundy values g(0..999) for all six novel games (JSON): discovery/grundy_novel_output.json