6 octal games, and which of them settle
Each row is an octal game: its code, the moves it allows, the first two dozen Grundy values, and whether a period was found in the values computed here. Guy and Smith surveyed these by hand in 1956 and conjectured that every finite octal game is eventually periodic. Seventy years and a great deal more arithmetic later, the rows in magenta are the state of that conjecture — not counterexamples, but sequences in which nothing periodic has yet appeared.
15 essays call
octal-survey. 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
4 distinct positions, harvested by drawing the figure again at the options each essay asked for.
| Position | Worth | Outcome | Drawn in |
|---|---|---|---|
·8f, a heap of 0 |
0 |
P | A period with a constant added · A code that climbs by three |
·8f, a heap of 1 |
0 |
P | A period with a constant added · A code that climbs by three |
·8f, a heap of 2 |
∗1 |
N | A period with a constant added · A code that climbs by three |
·8f, a heap of 3 |
∗1 |
N | A period with a constant added · A code that climbs by three |
Where it is called
Every one of these figures is a drawing of the same construction, so a correction to it corrects them all.
How it was found
The sequence nobody has settled
Guy and Smith surveyed the octal games by hand in 1956 and conjectured that every finite one is eventually periodic. Seventy years and a great deal more arithmetic later, some of them have settled and some have not — and the evidence for the conjecture is entirely that nobody has found a counterexample they were looking for.
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.
Impartial games
The values that keep arriving
A Grundy sequence that repeats uses finitely many values and stops needing new ones. Six thousand heaps into ·007 the count of distinct values is 187 and still climbing, and the share of heaps carrying something outside the twenty-two commonest rises from 32% in the first thousand to 85% in the sixth. The rare values a periodicity argument needs to thin out are getting commoner.
Impartial games
A period with a constant added
An octal code says what a player may do when removing k counters, in three bits; a hexadecimal code adds a fourth — leave three heaps — and the digits run to fifteen. Over twenty-two codes swept to six hundred heaps, five hexadecimal ones repeat with a fixed amount added each time round and no octal one does. Their values climb for ever and never repeat, so a search that looks only for repetition reports them unsettled.
Impartial games
A code that climbs by three
Five hexadecimal codes were known to repeat with a constant added, and every one of the five constants was a power of two — either a fact about exclusive-or or a coincidence over five cases. Sweeping all 255 two-digit codes settles it: seventy-one climb, seventy of them by 1, 2, 4 or 16, and one by three. The exception is ·3f, whose values are 3⌊n/6⌋ + (n mod 3) on every heap to twelve hundred.
Impartial games
The third digit
The rung below found 71 of the 255 two-digit hexadecimal codes repeating with a constant added rather than exactly, and asked whether the same share holds one digit wider. It rises. Of the 4,095 three-digit codes, 1,433 climb and 617 repeat exactly — seven in ten of the settled ones — so a saltus is the ordinary way a hexadecimal game settles and the exact repetition the octal survey was built to find is the special case.
Impartial games
The only way to split into three
Nineteen three-digit hexadecimal codes climb by three, and the rung below asked whether they share a form and what digits they have in common. The digits are exact: on eighteen of them the only way to split a heap into three is by taking exactly three counters, and taking three counters can do nothing else. The form is not shared — the eighteen carry four distinct sequences, and exactly one of the four counts in base three.
Impartial games
Two counters, and one displaced term
The rung below found four Grundy sequences in the odd-saltus class and asked which term each displaces and whether the digits predict it. They do — but there are two base-three counters and not one, chosen by whether a heap of one can be taken away. And there are three sequences rather than four: the fourth is the third with three isolated values, and was counted separately because its period had not settled.
Impartial games
A pattern that has not started yet
A pre-period was supposed to be rarer in this family than a defect. Two hexadecimal codes in five have one, 321 have a pre-period longer than their own period, and the code the rung below found slow takes fifty-four heaps to settle rather than two blocks — which is also the account of three defects the rung below recorded and could not explain.
Impartial games
The quantity that carried nothing
The rung below proposed predicting a pre-period's length from the saltus and the period. The saltus correlates with it at −0.03, which is nothing; the period correlates at 0.77 with a coefficient of one, so a pre-period is about one period long. The digit that predicts whether there is one predicts nothing at all about how long.
How it was found
Three bits of rule
An octal code is three bits a digit. The Grundy sequence it determines costs anywhere from one bit to a hundred and thirty-six — a factor of two hundred and seventy-two across rules that differ by a single digit — or it cannot be written down at all. Of four properties of the rule table tested against that, exactly one holds on every code that never settles: whether a move may leave two non-empty heaps. It is necessary, it is not sufficient, and nine codes carry it and produce answers smaller than their own rules.
Impartial games
A rare class exclusive-or respects
The rare values of ·007 were measured by rank — everything outside the twenty-two commonest — and found getting commoner. A sparse-space argument needs a different split: a rare class closed under nothing and a common class closed under exclusive-or, which is to say a parity of bits. Over every parity of every bit, ·007 and ·6 have no class that thins. Across the 79 growing octal codes of up to three digits, one does: ·354, whose odd values fall from 288 in its first two thousand heaps to seven in its last ten thousand.
Impartial games
The odd values keep coming
·354 is the one growing octal code of up to three digits whose values have a class that thins: 288 odd values in the first two thousand heaps, seven between ten and twenty thousand, the last of those at 18,908. A sparse-space argument needs that class to stop. Taken to a hundred thousand heaps it does not: 48 more odd values arrive after twenty thousand, every block of ten thousand holds some, and the last in range is at 99,600. They keep no schedule a remainder can see, their gaps are spread like arrivals, and most of them are one number, 37 — each one a heap where every split that could have reached 37 misses it.
What it costs
A repetition is a guess
Read an octal game's values one heap at a time and report the first pattern that fits, and the report is a guess that changes. Over the 291 short octal codes whose period can be proved, the guess is wrong 4,684 times before it settles; on ·45 it changes 181 times, is right from heap 538 and cannot be proved until heap 1,038. No false guess ever reaches the window that would certify it — the furthest gets 74 per cent of the way — and no fixed number of repetitions is a safe substitute, because the window asks for as many as the period's late start requires: two on some codes, twenty-seven on ·45.
What it costs
Growing is not climbing
The octal codes whose values grow were expected to be arithmetically periodic — repeating with a constant added each period — and to fool a reader with false climbs. Read for that pattern, the 220 octal codes of up to three digits with no certified period produce 246,048 readings in 1,200 heaps and not one holds for more than six periods. The false climbs are exactly as short as on the hexadecimal codes where the climb is real; the difference is that no right reading ever arrives, and the largest values grow more slowly than any constant climb allows.
The whole library · The position index · The figures that play back