A code that climbs by three

A hexadecimal code describes a take-and-break game in four bits per digit, and the fourth bit is the one that puts it outside the octal survey: a move may leave three heaps. A period with a constant added swept twenty-two codes and found a kind of repetition the octal survey was not written to look for — a sequence that climbs for ever and repeats its shape, so that $G(n + p) = G(n) + s$ for a period $p$ and a constant $s$ called the saltus.

Five codes did it, and their five saltuses were 1, 1, 2, 4 and 16. That page ended by naming the obvious question and declining to answer it:

Five codes give five saltuses — $1, 1, 2, 4, 16$ — and every one of them is a power of two. That is either a fact about exclusive-or, which is where the values come from, or a coincidence over five cases, and distinguishing those needs a wider sweep.

This is the wider sweep, and the answer is neither of the two on offer.

The sweep #

Every code of the form ·xy, with both digits ranging over the sixteen — 255 games, the whole two-digit family rather than a list somebody found interesting. Each is run to 360 heaps and searched for a period up to 60, with the arithmetic notion of a period rather than the strict one.

Sixty-six repeat exactly. Seventy-one repeat with a constant added. A hundred and eighteen do neither, which is a statement about the window and not about the games — several of those are known to settle further out, and the sweep says so rather than calling them wild.

The proportion is the first thing worth noticing. Twenty-eight per cent of the family climbs rather than repeats, so a survey written to find only strict periodicity would report those seventy-one alongside the genuinely unsettled ones and give a false picture of how much of the family is understood. That is what the rung below established on five codes and what this sweep establishes on seventy-one.

What the narrow sweep saw #

It is worth putting the two sweeps side by side, because the difference between them is a lesson about surveys rather than about games.

Twenty-two codes gave a correct picture of the phenomenon and a misleading picture of its shape. Every qualitative claim it made survives the wider sweep — that arithmetic periodicity exists, that it is a hexadecimal phenomenon, that a climbing sequence is completely described and looks unsettled to the wrong search. What did not survive is the one quantitative claim, and it did not survive because five is a small number and the five happened to agree.

That is the ordinary way a small survey misleads. It does not get the phenomenon wrong; it gets the exceptions wrong, because exceptions are rare and a small sample is where rare things are absent. One code in seventy-one is a rate at which a sample of five sees nothing about eleven times out of eighteen.

And the codes in the small sweep were not chosen at random. They were built by turning the fourth bit on in each digit of a code that was already understood, which is exactly the procedure that produces well-behaved games — a code adjacent to a known one is a code likely to inherit its regularity. ·3f is not adjacent to anything in that list.

The bounds, and why they are where they are #

The window is two numbers and both are load-bearing.

The heap bound is 360. Hexadecimal sequences cost more per heap than octal ones — a move may leave three heaps, so the option set is a triple loop and the work per heap is cubic rather than linear — and 255 of them is nine seconds of a build. Cutting to 300 loses ·28 and ·29, whose period is 53, and with them the whole saltus-of-sixteen row would have shrunk from three codes to one.

The period bound is 60. The same two codes are the reason. A search that stops at 45 reports them unsettled, and the census would then have said that sixteen is the saltus of a single code rather than of three — a difference that changes nothing about the finding and everything about how solid the pattern behind it looks.

Both bounds are stated in the sweep and the sweep is stated in every caption, because unsettled here means not settled inside this rectangle and never not settled.

No octal code climbs, and this is why #

The rung below noticed that of the twenty-two codes it swept, the five that climbed were all hexadecimal and none of the ten octal ones did. Ten is not many, and the natural reading was that the octal codes in that list happened to be the well-studied ones.

The wider sweep says it was not a coincidence. Sixty-three of the 255 codes have the fourth bit — a move may leave three heaps — set in neither digit, which makes them octal codes written in a wider alphabet. Not one of them is arithmetically periodic. Forty-four repeat exactly and nineteen find nothing in the window.

The mechanism is visible in the recursion. A move that leaves three heaps offers an option worth $G(a) \oplus G(b) \oplus G(c)$, and three-fold nim-sums reach values that two-fold ones from the same heap cannot — so the mex has more to climb over, and the sequence has somewhere to climb to. An octal game’s options at heap $n$ are nim-sums of at most two entries below $n$, and the ceiling that puts on the value is what makes a bounded, repeating sequence the ordinary outcome.

That is a statement about this sweep rather than a theorem, and it is a strong one: seventy-one out of seventy-one on one side and nought out of sixty-three on the other. It is also the reason the whole notion had to wait for the wider family — the octal survey was not failing to look for a saltus, it was looking at games that do not have one.

Seventy of seventy-one #

The pattern the rung below saw is real and it is nearly universal. Forty-eight codes add one, thirteen add two, six add four and three add sixteen: seventy of the seventy-one, all powers of two, across four orders of magnitude of saltus.

The reason to expect it is not superstition. Grundy values combine by exclusive-or — that is the whole content of the Sprague–Grundy theorem and the reason a nim-sum is the right arithmetic for a sum of heaps — and a power of two added to a number below it is exclusive-or with that power of two. A saltus that is a power of two is therefore a saltus that behaves like a bit being set, and the sequence’s climb reads as a counter in binary.

The mechanism is real and it is not a law. One code in the family climbs by three.

The exception #

·3f allows a player to take one counter and leave the heap whole or split in two, or take two counters and leave it in one, two or three pieces. Its Grundy sequence is

$$0\ 1\ 2 \quad 0\ 1\ 2 \quad 3\ 4\ 5 \quad 3\ 4\ 5 \quad 6\ 7\ 8 \quad 6\ 7\ 8 \quad \ldots$$

which is period six with three added each time round, from the very first heap.

There is no prefix and no irregularity: the pattern starts at heap one and the census checks it to twelve hundred. And it is not merely a period that has not broken yet — it has a closed form:

$$G(n) = 3\left\lfloor \frac{n}{6} \right\rfloor + (n \bmod 3)$$

which the census verifies at every heap to twelve hundred and throws if it fails at one. That is the difference between an observation and a description: a repetition is a claim that the future resembles the past, and a formula is a claim about every heap, checkable at any one of them.

The arithmetic in it is base three. The values below the constant are 0, 1 and 2, they count upward, and the constant lifts them by exactly their own range. Nothing about that is an exclusive-or, and reading the sequence as a binary counter with a bit being set is simply the wrong picture for this code.

What the exception costs #

The nice thing about an exception this clean is that it removes a hypothesis rather than complicating one.

A saltus that is a power of two is a saltus a sufficiency argument can work with: the standard route from an observed arithmetic period to a proved one is stated for a saltus that is a power of two, because that is the case in which adding the constant does not interfere with the values below it in the arithmetic the game’s options are built out of. ·3f has no such certificate available. It is regular to twelve hundred heaps, it has a formula that fits every one of them, and nothing in the standard machinery closes it.

That puts it in an unusual position on this site. A period is a proof is the essay about the moment an observation becomes a theorem — a window, a certificate, and a check that the recursion cannot see past the window. ·3f has the observation and the formula and not the certificate, so it sits between the settled sequences and the ones nobody has settled, in a class this site had no example of before.

What a saltus is for #

It is worth saying plainly what the constant does, because a sequence that never repeats is easy to mistake for a sequence that is not understood.

A game’s Grundy sequence is the whole of what a player needs: every impartial position collapses to a single Nim heap, and the value of a sum is the nim-sum of the parts. A sequence that repeats with period $p$ can be stored in $p$ numbers. A sequence that climbs with saltus $s$ and period $p$ can also be stored in $p$ numbers, together with $s$ — the same finite description, reached by a different route.

So arithmetic periodicity is not a weaker kind of solution than periodicity. It is the same kind, and the only thing it costs is that the values are unbounded, which matters to a program storing them in a byte and to nothing else.

What it does cost is the search. A survey that tests for repetition alone finds nothing in seventy-one of these codes, and reports as unsettled a family more than a quarter of which is completely described.

What the sweep does not say #

Four limits.

Two digits, not three. The family swept is ·xy, and the codes the literature is most interested in are longer. Whether a three-digit code can carry a saltus that is not a power of two, and whether the proportion of the family that climbs stays near a quarter, is the same census one digit wider and sixteen times as large.

One exception is one exception. ·3f says that the power-of-two pattern is not a law. It does not say what the law is, and a single case is not enough to guess one from — the honest reading is that the saltus can be a small integer and that powers of two are common because the values usually do combine by exclusive-or.

The formula is checked, not derived. $3\lfloor n/6 \rfloor + (n \bmod 3)$ fits twelve hundred heaps and is not proved here. Its shape suggests the proof — the option set of a heap of $n$ ought to be shown to contain exactly the values below $G(n)$ and to miss $G(n)$ — and that is an induction this page has not run.

And the window hides the interesting codes. The hundred and eighteen unsettled codes are where a genuinely wild sequence would be, and this sweep cannot tell a wild one from a slow one. The sequence nobody has settled is the standing example of how long that distinction can take.

One exception is a code and twenty are a class #

The single odd saltus found here is the sort of result that can be reported two ways, and which way is right depends on something this page cannot see.

As an exception, it is a fact about one code: $\\cdot 3\\mathsf{f}$ climbs by three, everything else in the two-digit family climbs by a power of two, and the natural next move is to explain that one code — look at its digits, find what is unusual, and account for it.

As a member of a class, it is a sample of size one from a population nobody has measured, and the natural next move is a wider sweep to find out how many there are.

The two programmes look similar and lead to completely different work. Explaining one code means understanding its sequence in detail; finding the class means enumerating more codes and looking for shared structure. And a single instance gives no evidence about which is right, because one exception is what both hypotheses predict at this width.

The wider sweep settles it decisively — twenty-one such codes at three digits, nineteen climbing by three, most sharing a period — and the class turns out to be the right frame. But the useful lesson is that the choice was not available from here: a lone exception is exactly the observation that cannot distinguish an accident from a family, and the honest response is to widen rather than to explain.

That is a general caution for a sweep over rule tables. A property found once in 255 codes has a rate of one in 255 and an uncertainty of the same size, and the difference between rare and the first of many is a sweep rather than an argument.

What it changes about surveying the family #

The practical consequence of the wide sweep is a change to what a survey should report.

A code that repeats exactly is settled. A code that repeats with a constant added is equally settled — the same finite description, reached by a different route — and a survey that looks only for exact repetition puts those seventy-one codes in the same column as the genuinely unknown ones. Twenty-eight per cent of this family is in that column when it should not be.

And the constant it repeats with should be reported rather than assumed. Five codes gave five powers of two, the pattern was strong enough to look like a rule, and one code in seventy-one breaks it. A survey that recorded arithmetically periodic without the saltus would have lost ·3f entirely, since nothing else about it is unusual: an ordinary two-digit code, a period of six, no exceptional prefix, and a formula.

The convention, named #

Normal play: the player who cannot move loses. All of this is about Grundy values, which exist because the games are impartial, and none of it survives a misère convention — where the values stop composing and a single number per heap is no longer enough.

A hexadecimal code ·d₁d₂… reads digit $k$ as a four-bit set: bit 1 permits taking $k$ counters and leaving no heap, bit 2 leaving one, bit 4 leaving two, bit 8 leaving three. The octal codes are the codes with the fourth bit off in every digit, and are swept here as the same family with a restriction.

The saltus is the constant added each time round. A saltus of nought is ordinary periodicity, and is reported as periodic rather than as an arithmetic period of nought, because the two are different claims and conflating them would put sixty-six codes in the wrong column.

Where the ladder goes next #

The hexadecimal anchor has two rungs: that the wider family repeats in a way the octal survey was not written to find, and now what the constant it repeats with can be.

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, which is a claim about how these games should be surveyed rather than about any one of them.

Two neighbours are worth the trip. A period is a proof is where the certificate is set out — what a window has to cover before a repetition stops being an observation — and ·3f is the case where the observation is unusually strong and the certificate is unavailable. And naming a game with a number is where the code notation is introduced, and it is worth rereading with this page beside it: the notation was designed for three bits, and the fourth bit brought a kind of answer nobody was looking for.