A period with a constant added

An octal code compresses a take-and-break rule into a string of digits. The digit $d_k$ says what a player may do when removing exactly $k$ counters from a heap, as a sum of three bits: take the whole heap, take $k$ and leave one heap, take $k$ and split the rest in two.

Three bits, so the digits run from $0$ to $7$, and the family is countable in the most literal sense — every finite string of octal digits names a game, and the survey that made the family famous was a sweep of the strings.

A hexadecimal code adds a fourth bit: take $k$ and split the rest into three heaps. The digits run to fifteen and the family is wider. What is interesting about it is not the width.

Two kinds of repetition #

A Grundy sequence is periodic when

$$G(n + p) = G(n)$$

from some point on. That is what the Guy and Smith survey looked for, it is what a period is a proof is about, and it settles a game completely: check the pattern for two full copies past its start and every heap of every size is known for ever.

It is arithmetically periodic when

$$G(n + p) = G(n) + s$$

for a fixed $s$, called the saltus. The values never repeat — they climb without bound — and the sequence is nevertheless described completely by one period and one constant.

The distinction is not a refinement. The two properties are incompatible for a non-zero saltus, and a game with an arithmetic period is a game that a plain period search will report as unsettled while being entirely solved.

What the fourth bit does #

The bit is worth stating in the vocabulary of the mex, because the effect is direct.

A move leaving one heap contributes that heap’s Grundy value. A move leaving two contributes a nim-sum of two entries. A move leaving three contributes a nim-sum of three, and the set of triples of positive integers summing to $n - k$ is quadratic in $n$ where the pairs are linear.

So a hexadecimal game has many more options per heap and its mex is taken over a much larger set. As the essay on Lasker’s Nim points out, adding options to an impartial game can only move a value upward, and only by filling the gap the mex was about to find. A great many extra options is therefore not automatically a great many changes — most of them land above the gap and are invisible.

What the extra bit does supply, in quantity, is large values. A nim-sum of three entries can be much bigger than either of the two entries a pair produces, so the values available to fill a gap reach further up, and the sequence has room to climb rather than to cycle.

That is the mechanism behind the saltus, stated loosely. Where an octal game’s options come from a bounded neighbourhood of values and the sequence therefore settles into a cycle, a hexadecimal game’s reach grows with the heap, and the sequence can grow with it while keeping a shape.

The census #

Twenty-two codes, six hundred heaps each, one search.

Octal: four periodic, six unsettled, none arithmetically periodic. The periodic ones are $\cdot 07$ and $\cdot 137$ at period thirty-four, $\cdot 17$ at thirty-four, and $\cdot 77$ — Kayles — at twelve. The unsettled six include $\cdot 007$, which is the most famous open case in the family.

Hexadecimal: four periodic, five arithmetically periodic, three unsettled. The arithmetic ones are $\cdot 8$ with period three and saltus one, $\cdot 8\mathsf{f}$ with period seven and saltus four, $\cdot 9\mathsf{f}$ with period three and saltus two, $\cdot \mathsf{bf}$ with period one and saltus one, and $\cdot 28$ with period fifty-three and saltus sixteen.

The last of those is the striking one. A period of fifty-three with sixteen added each time round is a description short enough to write on a line and long enough that nobody would find it by looking at the sequence. Its largest value in the six-hundred-heap window is 181, so the sequence has climbed a long way while keeping a shape, and it is still climbing at the edge.

The two extremes of the arithmetic family #

The five arithmetic codes span the range the property can occupy, and the two ends are worth looking at directly.

$\cdot \mathsf{bf}$ has period one and saltus one. A period of one means every heap’s value is one more than the previous heap’s, so the sequence is $G(n) = n - c$ for a constant, from heap four onward. That is as describable as a sequence gets — it is the identity, shifted — and a plain period search reports it unsettled, because no two terms are ever equal.

$\cdot 28$ has period fifty-three and saltus sixteen. Fifty-three terms repeat with sixteen added, from heap one, and the pattern holds for every one of the eleven complete copies in the window. Nobody would find that by inspection and nothing about the digits $2$ and $8$ suggests fifty-three.

Between the two extremes the family behaves as one would hope: the period and the saltus are independent, small periods occur with small saltuses and with large ones, and there is no visible relation between a code’s digits and either number.

What the sweep is evidence for #

Every claim in the census is a claim about a window of six hundred heaps and about nothing else, and the two directions are not equally safe.

“This sequence has a period of $p$ with saltus $s$” is checked from the start of the pattern to the end of the window, which for $\cdot 28$ is nine full copies and for $\cdot \mathsf{bf}$ is hundreds. It is strong evidence and it is not a proof. The standard sufficiency condition for octal games — check two periods past the start and the pattern continues for ever — has an arithmetic-periodic analogue, and it depends on the code’s length in a way a bare window does not establish.

“This sequence is not settled” is much weaker. It says a search over periods up to sixty found nothing in six hundred terms. A longer period, or a later start, or a larger window would each change the answer, and the octal family’s history is full of sequences that looked unsettled for a long time and were not.

The alphabet test above has a striking consequence for arithmetic periodicity, and it is worth noticing: an arithmetically periodic sequence with a non-zero saltus uses infinitely many values. So the alphabet curve for such a sequence climbs for ever, and every test on this site that reads a still-growing alphabet as evidence against periodicity is reading it correctly and saying nothing about whether the game is solved.

That is the trap the two definitions set. The site’s own sparse-space essay reports 187 values at six thousand heaps for the code $\cdot 007$ and treats the growth as a proof that no period has begun. It is one. It is not a proof that no arithmetic period has begun, and the search that would settle that is a different search.

Solved, unsolved, and the third thing #

The census sorts twenty-two codes into three boxes and only two of them are outcomes.

Settled with a period. The game is solved: a table of one period answers every heap of every size, and what “solved” means is satisfied in its strongest sense.

Settled with an arithmetic period. The game is equally solved and the table is one period plus a constant. Nothing is weaker about it. What is different is that the answer is unbounded, so no finite table of values exists — only a finite table of values plus a rule for how they grow.

Not settled in the window. This is not a box at all. It is the absence of a result, and the six octal codes and three hexadecimal codes in it are in it for want of a longer search or a cleverer one.

The reason to insist on the distinction is that the three are constantly collapsed into two. A reader told that a sequence “has no period” reasonably concludes the game is unsolved, and for an arithmetically periodic sequence that conclusion is simply wrong.

What the codes cannot say #

A code is a rule table, not a game. Two codes can name games nobody would call similar, and one code can be a game somebody plays — $\cdot 77$ is Kayles, $\cdot 137$ is Dawson’s chess — or a game nobody has ever played. The family is a search space rather than a collection.

A hexadecimal game may not correspond to anything. Dawson’s chess turned out to be an octal game and that is the family’s best advertisement; nothing comparable is known for the wider one.

The bit is about heaps, not about boards. “Leave three heaps” makes sense for a row of counters and its meaning for a real game depends on what a heap is. A hexadecimal code that corresponds to a game anybody plays is rarer than an octal one, which is part of why the wider family has been swept less.

The window is six hundred. That is the weakest of the four, because it is the one every other claim on the page inherits, and it is the one a wider window can actually settle. So the same sweep is run again to sixteen hundred heaps, and the two classifications are set side by side.

The window, widened #

The interesting thing about widening a window is what a widened window can and cannot do. It can break a claimed period — one disagreement anywhere past the old edge and the classification was wrong. It cannot confirm one, because the next heap out is always unexamined. So the deeper sweep is a test the census could fail, run for that reason and not for reassurance.

The nine unsettled codes are the ones the wider window says least about. Their largest values roughly double — $\cdot 007$ from 35 to 74, $\cdot 37$ from 21 to 50 — and a search over periods up to sixty still finds nothing in either window. That is one thousand more terms of the same negative result, which is worth having and is not a different kind of evidence.

The cost of the extra bit #

One practical difference is worth recording, because it is the reason the wider family has been swept less and the reason the census is drawn at six hundred rather than at sixteen.

Computing an octal sequence to $n$ heaps costs, per heap, one pass over the ways of splitting into two — which is linear in the heap. Computing a hexadecimal sequence costs a pass over the ways of splitting into three, which is quadratic. So the whole sweep is cubic where the octal one is quadratic, and the constant is not small.

That is a prediction rather than a description, and the two windows above test it. Sixteen hundred heaps is two and two-thirds of six hundred, and a cubic says the deeper sweep should cost nineteen times the shallower one. Measured here it costs about twenty. The exponent is the thing being checked and it is the thing that comes out right; the factor of twenty is why the essay’s figures are drawn at the shallower depth and its classifications checked once at the deeper one rather than the other way round.

That cost is what has kept the hexadecimal family thin in the literature relative to the octal one. It is not that the games are harder to decide: a heap of a given size takes a mex over its options like any other, and the enumeration of those options is simply one power larger. The historic surveys were run on machines where an order of magnitude in a sweep decided what got swept, which is the ordinary way a search space acquires a shape that has nothing to do with its subject.

Who named it, and when #

The octal notation is Guy and Smith’s, from their 1956 survey, and the whole idea of naming games by a rule table so that the family can be searched is theirs. Hexadecimal codes are a natural extension and were introduced later as the obvious next digit; the “all-but” codes, in which a move may take from every heap at once, are another direction the same idea goes.

Arithmetic periodicity is the property that made the extension worth having. Austin’s thesis in the 1970s established the sufficiency conditions — how far a sequence must be checked before a claimed arithmetic period is proved — and the property has since turned up across the wider family often enough to be a standard thing to look for.

The historical point worth keeping is that the survey found what it was looking for. Guy and Smith looked for periods, found periods, and conjectured that every finite octal game has one. A search that had been written to look for arithmetic periods as well would have reported the same octal games and a different picture of the wider family, and the reason the octal family looks the way it does in the literature is partly a fact about what the first search asked.

The digit that is missing from both notations #

Both notations describe what may happen when $k \ge 1$ counters are removed. Neither has a place for $k = 0$ — a move that removes nothing and breaks a heap — because the string conventionally starts after the point.

That digit is not exotic. Lasker’s Nim is exactly the game with a leading $4$ and all threes after the point, and its Grundy sequence has a four-line closed form: the identity with every fourth pair transposed. So the column the notation cannot address contains at least one game with a nicer answer than anything in either sweep above.

The general point is about search rather than about notation. A family defined by a notation is searched by enumerating the notation, so what the notation cannot write is not searched — and the reason a column is empty is as often a fact about the string as about the games.

Why a sequence cannot have both #

The claim above — that the two properties are incompatible for a non-zero saltus — is asserted where it is made, and it is worth the three lines it costs, because the incompatibility is what makes the two searches genuinely different searches rather than one search with a looser test.

Suppose a sequence is eventually periodic with period $p$ and eventually arithmetically periodic with period $q$ and saltus $s$. Beyond the later of the two starts both hold, so take a heap $n$ there and step forward by $pq$. Reading it as $q$ applications of the first rule gives $G(n + pq) = G(n)$. Reading it as $p$ applications of the second gives $G(n + pq) = G(n) + ps$. So $ps = 0$, and since $p \ge 1$ the saltus is nought.

Which says the two boxes in the census are disjoint by arithmetic rather than by observation, and it says something sharper about what a window can establish. A sequence with a non-zero saltus is unbounded, so it uses infinitely many values and no finite table of values describes it. A search that reports no period found in six hundred heaps has, on such a sequence, reported a theorem — there is no period, ever — while saying nothing whatever about whether the game is solved. The one negative result a window can honestly deliver is the one that matters least.

Where the ladder goes next #

The first rung out is the sufficiency condition, stated and applied: how far each of the five arithmetic sequences here has to be checked before its period is established rather than observed. That turns five observations into five theorems and it is a computation rather than an insight.

The second is the saltus as a quantity, and this page’s five cases — $1, 1, 2, 4, 16$, every one a power of two — turn out to be a small sample of a much less tidy fact. The code that climbs by three widens the sweep to all 255 two-digit codes and finds exactly one saltus that is not a power of two; the third digit widens it again to all 4,095 three-digit codes and finds twenty-one, nineteen of them climbing by three with a period of nine. So the pattern the five cases suggest is real and is not a law, and the exceptions are a family rather than a scattering — which is a better outcome than either answer the question was posed with.

The same sweep overturns the impression this page’s census leaves about how common the behaviour is. Twelve hexadecimal codes here give five arithmetic and four exact; at three digits it is 1,433 climbing against 617 repeating exactly, 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.

And the third question is the octal survey’s own, sharpened by the wider family: is there a finite code with no eventual period of either kind? The Guy and Smith conjecture says no for octal codes. Nobody has conjectured anything for the wider family, and the wider family is where a counterexample would be easiest to hide.