Subtraction of 1, 3, 4 — and the window that proves the period
The Grundy values of a subtraction game, with the window that certifies the period marked. Everything after the window follows from it by induction, because a value is a mex over values at most one move back — so a finite check settles the whole infinite sequence, and the thousands of further values computed here agree with a claim that was already proved.
6 essays call
period-window. The drawing above is what it returns with no arguments at all; every
call below passes it something, because a placement that passes nothing draws whichever
member of the family the generator happens to default to rather than the one its essay argues
about.
The positions it draws
35 distinct positions, harvested by running this generator again at the options each essay passed it.
Where it is called
Changing this generator changes every one of these figures.
How it was found
A chess problem that turned out to be an octal game
Dawson posed it in 1934 as a puzzle about pawns. It is the octal game ·137, its Grundy sequence is eventually periodic with period 34 from heap 52 — and the word doing the work in that sentence is eventually, because five values below the start disagree with their repeats and always will.
Impartial games
Take one, three or four
A heap and a list of legal takes. It is the smallest interesting impartial game there is, and the only family in the subject where eventual periodicity is not observed, not conjectured, but guaranteed — with a bound on when it must appear.
What it costs
Four values, and the sequence is settled for ever
The Grundy values of a subtraction game repeat with period 7, and proving it needs a window of exactly four of them — one for each size of move the game allows. Everything past the window follows by induction. A finite computation has settled a claim about every heap there will ever be.
Impartial games
The period is small and the proof does not say so
Every subtraction game repeats eventually — that is a theorem, and its proof gives a bound of sixteen thousand for a three-move set. Over 112 sets the longest period measured is twenty-two. The proof and the fact are four orders of magnitude apart, and the rule of thumb that closes the gap is broken by one set in the sweep.
Particular games
Two players, two lists
Give each player their own list of how many counters they may take and the impartial theory stops applying. What survives is the outcome: it settles into a repeat, for every pair of lists, and that is a theorem. What does not survive is the value — on four of six pairs swept it has no repeat inside sixty heaps, and the birthdays are still climbing at the edge of the window.
How it was found
What the arithmetic cost in 1956
The rung below ends by respecting a hand computation without pricing it. Priced in the operations a person actually performs, ·137's certificate is 7,919 of them — and the same sweep says ·47's is sixty-three times that, that a splitting move is what makes the cost quadratic, and that seventeen of sixty-four codes have no certificate at any price.
The whole library · The position index · The figures that play back