The third digit

An octal code says what a move may do to one heap; a hexadecimal code says what it may do when the move is allowed to leave three heaps rather than two. A period with a constant added is where this site meets the behaviour the wider family has and the octal survey was not written to find: the sequence repeats not exactly but with a fixed amount added each time round, and the amount is called the saltus.

The code that climbs by three swept all 255 two-digit codes: 71 climb, 66 repeat exactly, 118 settle nothing inside the window, and one of the 71 climbs by three rather than by a power of two. It closed by naming the sweep that would say what any of that means:

The rung above is the three-digit sweep, and its interest is the proportion rather than the exception. If a quarter of ·xy climbs, the question is whether a quarter of ·xyz does — and if it does, arithmetic periodicity stops being a curiosity of the wider family and becomes the ordinary way a hexadecimal game settles.

It does, and by more than the question expected.

The count #

Four thousand and ninety-five codes, sweeping each to 160 heaps and looking for a repetition with a constant added:

• 1,433 climb — they repeat with a saltus;
• 617 repeat exactly — saltus nought, which is what an octal game does;
• 2,045 settle nothing inside the window.

The last number is half the family and it is why the comparison has to be made carefully. Of all codes, 35 per cent climb at three digits against 28 at two — a modest rise. Of the codes that settle, 70 per cent climb against 52 — a large one. Both readings point the same way and the second is the one the rung below’s question was about, since a code that has not settled has not shown which kind of settling it will do.

What that changes about surveying these games #

The octal survey — Guy and Smith’s, and every table since — asks whether a sequence is eventually periodic, and records a period and a preperiod when it finds one. Applied to the hexadecimal family that question has the wrong shape: it can only find the 617, and it reports the 1,433 as unsettled.

So a survey of hexadecimal games that looks for exact periods is looking for the rarer half of the settled behaviour. That is a claim about method rather than about any one game, and it is what the proportion buys. A table built the octal way would show 15 per cent of these codes settled and 85 open; the same sweep looking for a saltus as well shows 50 per cent settled.

That the difference is this large is the finding. At two digits the two methods differ by 71 codes out of 255, which reads as a curiosity of a wider family; at three digits they differ by 1,433 out of 4,095, which reads as the wrong instrument.

One more consequence is worth drawing, because it changes what an open problem means here. A code reported as no period found by an octal-style survey may have a perfectly regular sequence that the survey’s question cannot express. Among these 4,095 codes that is not a hypothetical: 1,433 of them are exactly that case, and every one would have been filed as unsettled by the older method.

That is a different kind of open problem from the one the sequence nobody has settled describes. There the sequence resists every question anybody has asked of it; here the sequence answered a question nobody asked.

The exception has become a family #

At two digits exactly one code climbed by something other than a power of two, and the rung below treated it as an exception in need of an explanation: ·3f, climbing by three with a period of six, whose sequence is three counted in base three, twice over.

At three digits there are twenty-one such codes, and they are not scattered. Nineteen climb by three, one by five and one by six; most of the nineteen share a period of nine. So ·3f is a member of a family, and the family has a shape — a period three times the saltus, which is the signature of a sequence counting in base three the way ·3f does.

That is a better position than the rung below was in. A single exception invites an explanation of that one code; twenty with a common period and a common saltus invite a description of the class, and the class is now large enough for one to be worth writing.

The bit that buys a saltus, again #

A hexadecimal digit is four bits and the fourth of them is leave three heaps. A code with no digit of eight or more is an octal code wearing a hexadecimal spelling, and there are 511 of them among the 4,095.

Not one of them climbs. Two hundred and fifty repeat exactly, 261 settle nothing, and the arithmetic column is empty — exactly as it was at two digits, where the same test came out at 63 codes and none.

So the mechanism the rung below proposed survives sixteenfold magnification: a saltus is something the third heap buys, and nothing else in a rule table produces one. That is unusually clean for this subject, where a rule table’s digits normally sort games into families nobody can characterise — Kayles is $\cdot 77$ and has no formula, Lasker’s has one, and nothing about the digits says which is which.

Why a third heap should do it #

The mechanism has an argument behind it and the argument is worth stating, because the census cannot supply one.

A move that leaves two heaps splits a game into two independent parts whose values nim-add. A move that leaves three introduces a third part, and the nim-sum of three values behaves differently from the nim-sum of two in one specific way: it can produce a value larger than any of the parts, repeatedly, as the heap grows. That is the raw material a saltus is made of — a sequence whose values grow without bound but grow regularly.

An octal game cannot do it because its move leaves at most two heaps, and the values it can reach at heap $n$ are bounded by a function of the values below in a way that forces boundedness once a period starts. That is a sketch and not a proof; what the census establishes is that the boundary the sketch describes is exactly where the behaviour changes, on 4,350 codes across the two widths.

What the sweep cannot see #

Half the codes settle nothing inside the window, and the honest reading of that is not these games are aperiodic. It is this window is 160 heaps. A code with a period of two hundred is indistinguishable here from one with no period at all, and a period is a proof sets out what a certificate would have to cover before a repetition counts as established.

The window’s size was chosen by measurement rather than by taste. Sweeping to 200 and to 240 gives 621 and 628 exact periods, 1,443 and 1,459 climbing ones — and 69.9 per cent of the settled codes climbing at every length. The cost rises as the square of the window, from 17 seconds to 55, so the shorter one is used and the longer ones stand as the check that the shares are not an artefact of it.

What a longer window would change is the denominator, not the ratio. Codes move out of the unsettled column as the window grows, and they have moved into the two settled columns in the same proportion at each of the three lengths tried.

What it costs to ask #

The sweep is 4,095 games evaluated to 160 heaps each, which is 655,200 Grundy values and about seventeen seconds. That is worth stating because the cost is the reason this question waited: the two-digit sweep is 40,800 values and runs in a second, and a four-digit sweep is 65,535 codes and about an hour at the same window.

The scaling is the sixteenfold growth of the family multiplied by whatever window the question needs, and the window is the part that can be argued about. Doubling it to 320 heaps would quadruple the arithmetic and would move perhaps two hundred codes out of the unsettled column — a poor trade for a page about proportions, and the right trade for a page about any one code.

A census whose cost is dominated by the codes that will not settle is a census with a natural stopping point, and this one is at it: half the family is unsettled at every window tried, and each doubling of the window costs four times as much to move a few per cent of them.

What a saltus is, at the board #

The vocabulary is worth grounding, because arithmetic periodicity sounds like a property of a table and is a statement about play.

A game whose Grundy sequence repeats exactly is one where a heap of $n + p$ counters plays like a heap of $n$: the extra $p$ counters are worth nothing, and a player facing a large heap can reduce it mentally to a small one. That is what an octal game’s period buys, and it is why a period is worth hunting.

A saltus says the extra counters are worth something, and always the same something. A heap of $n + p$ plays like a heap of $n$ with $s$ added to its Grundy value, so a large heap is not equivalent to a small one — but the difference is a constant, and a constant is as good as nothing once a player knows it. The reduction is still available; it just carries a correction.

A player can use that. Knowing a code’s period and saltus turns any heap into a small heap and a piece of arithmetic, which is the same thing an octal game’s period buys with the arithmetic left out.

So the finding of this page is not a technicality about tables. It says that in the wider family most settled games are reducible with a correction rather than reducible outright, and a survey that only recognises the second kind will report most of them as unsettled.

The three-digit family is where that stops being a curiosity, because it is large enough that the two kinds can be counted against each other. At two digits it is 71 against 66 — a near tie, easily read as two comparable behaviours. At three it is 1,433 against 617, and the reading changes.

Why a share is the right statistic here and a count is not #

The headline is a proportion — seven in ten of the settled codes climb — and it is worth saying why that is the number to quote rather than the 1,433.

A count of codes with some property is a count over an arbitrary population. There are 4,095 three-digit codes because there are three digits and sixteen values, and nothing about the family says that population is meaningful: the codes are strings, most of them describe games nobody has played, and a great many describe the same game under different spellings.

What survives the arbitrariness is the ratio between two counts taken over the same population. Of the codes that settle, how many settle with a saltus? is a question whose answer does not depend on how many codes there happen to be, and it is the question a survey method is judged by — because a survey looking only for exact periods reports the complement of that ratio as its coverage.

That is the finding this page is really about, and it is a claim about method rather than about any game. A survey of hexadecimal games that looks for exact periods is looking for the rarer half of the settled behaviour, and the table it produces shows 15 per cent settled where the same sweep asking both questions shows 50.

The count is still worth reporting, and for a different reason: it says the sweep is large enough for the ratio to mean something. A proportion over twenty codes would be an anecdote. Over 2,050 settled ones it is a measurement, and the two numbers are doing two different jobs.

What this does not say #

Four limits.

A found period is not a proved one. Every row here is a repetition observed inside a window, checked for enough repeats to be worth reporting and not certified. The distinction is the whole subject of a period is a proof, and it applies to all 2,050 settled codes here.

Three digits, and the family is infinite. There are 65,535 four-digit codes and the sweep would take an hour at this window. Whether the climbing share keeps rising is the obvious next question and nothing here answers it — though the mechanism says it should, since a fourth digit adds leave four heaps and more parts is more of what produces a saltus.

The saltus classification depends on the period found. A sequence with a period of nine and a saltus of three also has a period of eighteen and a saltus of six, and the search takes the smallest period. That convention is what makes the saltus table readable and it is a convention.

And a share is not a game. Seventy per cent of settled codes climbing says how these games behave in bulk; it says nothing about the game somebody actually wants to play, whose code may be one of the 2,045 that settle nothing at all.

The convention, named #

Normal play, one heap of $n$ counters, a code read digit by digit.

A hexadecimal code ·d₁d₂d₃… gives, for each amount $k$ taken, four bits saying whether the move may leave nought, one, two or three non-empty heaps. The fourth bit is what the octal family does not have.

A sequence is arithmetically periodic with period $p$ and saltus $s$ when $G(n + p) = G(n) + s$ for every $n$ beyond some start. Ordinary periodicity is the case $s = 0$, and it is reported in its own column throughout rather than folded in.

Settled means a repetition was found inside the window; unsettled means none was, and it is not a claim that none exists.

One number is worth carrying past all the others. Seven in ten of the settled three-digit codes climb, and the octal survey’s question cannot see any of them. A method that reports the commoner behaviour as unsettled is not a conservative method; it is the wrong question asked carefully.

Where the ladder goes next #

The hexadecimal anchor has three rungs to here, and the two above take the twenty-one odd-saltus codes this page finds and ask what they have in common.

The only way to split into three answers the digits question exactly and the form question negatively. On eighteen of the nineteen the only way to split a heap into three is by taking exactly three counters, and taking three counters can do nothing else — a condition on two digits, stated in one clause. The form is not shared: those eighteen carry four distinct Grundy sequences between them, and exactly one of the four is a base-three counter, so most of the class is aliases rather than a shape.

The condition is also nowhere near sufficient. A hundred and twenty-eight codes satisfy it and eighteen of them climb by three, so the digits pick the class out and do not explain it — which is the ordinary fate of a rule-table condition in this family and worth knowing before reading the count as a characterisation.

Two counters and one displaced term then asks which term each of the four sequences displaces, and corrects the count on the way. There are three sequences rather than four — the fourth is the third with three isolated values, counted separately only because its period had not settled — and there are two base-three counters rather than one, chosen by whether a heap of one can be taken away.

So the class this page opens is smaller and tidier than its own count suggests, and the tidying came from looking at the sequences rather than at the codes. Twenty-one codes, nineteen with a saltus of three, eighteen sharing a digit condition, three distinct sequences: each step down is a different object being counted.