Two counters, and one displaced term

The only way to split into three found eighteen hexadecimal codes sharing one condition on their digits and carrying four distinct Grundy sequences between them, exactly one of which is a base-three counter. It closed on the other three:

The rung above is the defects. Three of the four sequences are a base-three counter with one term changed, and the fourth is the counter itself … Which term is displaced, and whether the displacement is predictable from the digits, is a question about four nine-term periods and is small enough to answer by hand.

The displacement is predictable. The description needs one correction and produces another.

There are two counters #

The base-three counter $0\,1\,2\,0\,1\,2\,0\,1\,2$ has a partner with nought and one exchanged, $1\,0\,2\,1\,0\,2\,1\,0\,2$, and two of the four periods sit on each.

Which one a code follows is decided by a single fact about its rules: whether a heap of one counter can be taken away entirely. A heap of one has Grundy value nought when the only legal take leaves a heap behind, and one when the heap can be removed — so the first term of the sequence is nought or one, and everything after it follows.

In the codes that is the parity of the take-one digit. The eight codes beginning $6$ and the six beginning $2$ have even take-one digits and follow the plain counter; the four beginning $1$ or $3$ have odd ones and follow the swapped counter.

That is the correction to the rung below’s description. A base-three counter with one term changed is right once the counter is allowed to be either of two, and the two are one bit apart in the rules.

One displaced term #

Against its own counter, each period differs in almost nowhere:

• the six codes beginning $2$ — nowhere at all, the counter outright;
• the eight beginning $6$ — at the seventh place, where a nought becomes a 3;
• the three with a take-two digit of $6$ — at the eighth, where a nought becomes a 3;
• and .129 — at the sixth and the eighth, which is the exception.

The displaced value is 3 in every case, which is the saltus — the amount the whole period climbs by each time round. So a defect is not an arbitrary value; it is one block’s worth of climb arriving one place early, and the term it displaces is a nought.

The saltus carries the defect forward, so a single displaced term in a nine-term period is a displaced term in every block for ever. That is what makes a one-term description of a sequence worth having: the whole infinite sequence is nine numbers, a constant, and one exception.

The digits predict it #

The class contains eleven distinct pairs of first two digits, and each pair determines the sequence:

• take-one $2$, with any take-two below $4$ — the plain counter, no defect;
• take-one $6$ — the plain counter, defect at the seventh place;
• take-two $6$, with an odd take-one — the swapped counter, defect at the eighth;
• take-one $1$ and take-two $2$ — the swapped counter, defects at the sixth and eighth.

So the answer to is the displacement predictable from the digits is yes, and the honest form of the answer is a table of eleven entries rather than a rule. Eleven is every pair the class contains, so a rule fitted to them would be fitted to everything there is; what the table shows is that the map exists and is short.

There is a partial reading of it. The digit 6 is bits 2 and 4 — a take that may leave one heap or two — and it is the digit that carries a defect, in whichever place it sits: in the take-one digit the defect is at the seventh place, in the take-two digit at the eighth. The digit 2 is bit 2 alone, a take that leaves exactly one heap, and it carries no defect. So the defect follows the split, one place further along when the split costs one counter more.

Why a nought is what gets displaced #

The defects have one thing in common that is worth reading rather than tabulating: the displaced term is always a nought, and it always becomes the saltus.

A nought in a Grundy sequence is a losing heap — a heap the mover would rather not be handed. A value equal to the saltus is, in an arithmetic sequence, the value the next block’s first term would have. So a defect is a heap that ought to be a loss and is instead worth what a heap one full period larger is worth.

The reading is that the extra option — the split the digit 6 licenses — gives the mover somewhere to go from a heap that would otherwise have been dead, and where it takes them is into the value the sequence has not reached yet. The mex sees a set of options one value richer than the counter’s, and returns the next value up.

That also accounts for the two positions. A split costing one counter reaches back one place further than a split costing two, so the take-one digit’s defect sits at the seventh place and the take-two digit’s at the eighth — one place apart, in the direction the extra counter costs. It is not a derivation, because the mex has to be computed to see it, but it is the right shape and it is the only structure in the table that is not a listing.

A period is a proof is the standard this ladder holds a periodicity claim to, and the reading above does not meet it. What it does is say which measurement would: computing the option sets at the seventh and eighth heaps of each block and checking that the extra option is the one the reading names.

The third digit does nothing #

Every one of the eleven pairs appears in the class with a third digit of both $8$ and $9$ — that is, with and without the option of taking three counters and emptying the heap — and the Grundy sequence is identical either way.

That is worth stopping at, because the class is defined by a condition on the third digit. The only way to split into three found that every code in it has its three-take carrying the split-into-three bit and no other take carrying it — a condition entirely about the third digit — and the sequence turns out to be a function of the first two.

So the third digit decides membership and the first two decide which sequence. A code’s admission to the class and its behaviour inside it are settled by different parts of its own name.

That is a cleaner separation than it sounds, and it explains a count the rung below reported and could not account for. A hundred and twenty-eight codes satisfy the third-digit condition and only eighteen of them climb by three — because the condition is necessary for admission and says nothing about which of the first two digits the code has, and the first two are what decide whether an arithmetic period appears at all.

The fourth sequence is the third one #

.129 was counted as a family of its own, and it is not one.

Run .129 and .169 to four hundred heaps and they disagree at exactly three of the 399 — heaps 6, 15 and 54 — and agree at every other one. .129’s value is the lower at all three.

The rung below counted them separately because a family was keyed on a code’s first sixty Grundy values, and .129’s period has not settled inside them: its first block is $1\,0\,2\,1\,0\,0\,1\,3\,2$ and its second is that plus three except at one place, and only from the third block on does it agree with .169. A key taken at sixty terms sees the pre-period; a key taken at four hundred does not.

That is a fault worth naming rather than fixing quietly, because it is the kind that produces a bigger answer than the truth and therefore looks like a finding. A census keyed on a prefix over-counts families: two sequences that eventually coincide are two entries until the key is long enough to see it. The rung below’s four was an over-count of exactly that kind, and the only reason it was found is that this page asked what the four had in common and one of them would not fit.

So the class has three eventual sequences, not four, and the description the rung below was reaching for is exact rather than nearly so: the odd-saltus class is two counters and one displaced term, with eighteen codes distributed over three sequences.

What a class of eighteen codes is worth #

The anchor has now spent three rungs on eighteen codes out of 4,095, and it is worth saying what that buys, because the ratio looks bad.

The eighteen are the codes with an odd saltus, and the third digit found them by sweeping every three-digit code and looking for arithmetic periodicity. Twenty-one codes climb by a saltus that is not a power of two, against the two-digit sweep’s one — so the class is the whole of what a third digit adds to a phenomenon that barely existed without it.

What this page adds is that the eighteen are not eighteen answers. They are three sequences, and the three are one shape with two perturbations, and the shape is a base-three counter. So the third digit’s whole contribution to arithmetic periodicity, over the entire family it opens up, is one sequence and two dents in it.

That is a small answer and it is a complete one, which is the trade this anchor keeps making. The code that climbs by three is the single code the two-digit sweep found; this class is what happens when the same question is asked one digit wider, and the answer is that the family gets bigger and the behaviour does not.

The general reading is worth carrying because it is the opposite of what a wider family usually gives. Adding a digit to the notation multiplies the codes by sixteen and adds three sequences — so the behaviour the notation can express is not growing anything like as fast as the notation is. Octal games is where the notation is introduced and where its promise of generality is set out, and this is a small measurement of how much of that promise a third digit redeems.

Counting sequences is harder than counting codes #

Two corrections arrive together here — four sequences becoming three, one counter becoming two — and both are miscounts of the same kind. It is worth naming the kind, because a sweep over rule tables invites it.

A code is a string and a sequence is an object, and the map between them is many-to-one in a way nobody controls. Several codes give the same Grundy sequence, so a count of codes with a property is not a count of behaviours; and one sequence can be observed as two, if a sweep’s window is too short for its period to settle and the unsettled tail is recorded as a separate shape.

Both failures happened here and they pull opposite ways. Counting codes over-counts the behaviours, because aliases are counted separately. Counting sequences by their observed period over-counts again, because a sequence whose period has not yet declared itself looks like a different sequence from the same one seen further out.

So the honest object to count is a sequence identified by enough of itself to be sure, and enough is a decision about the window rather than about the codes. The fourth sequence here differs from the third by three isolated values and was counted separately for exactly that reason.

The instruction that follows is short and applies to every sweep in this family. Deduplicate on the sequence, not on the code, and check the deduplication at two window sizes — because a distinction that disappears when the window grows was never a distinction, and a sweep run at one depth has no way to tell.

What this does not say #

Eleven pairs is the whole population. The digit table is not a rule extrapolated to codes outside the class; it is a listing of what the class contains, and a code with a take-one digit of $4$ would be outside it. Whether the reading — the defect follows the split — survives to a wider family is untested.

Four hundred heaps is not for ever. .129 and .169 agree at 396 of the first 399 heaps and eventual periodicity is not proved for either. A period is a proof is the site’s standing warning here: a sequence that has repeated for four hundred terms has repeated for four hundred terms.

The three isolated defects have no account. Heaps 6, 15 and 54: the first two are nine apart and the third is not, and nothing here explains why there are three or why they sit where they do. They are reported because they are what is there, and a defect with no account is the honest form of a measurement that found one.

And the parity reading is about the first term, not the sequence. A heap of one can be taken away, so the sequence starts at one rather than nought explains the first value; that the swap then propagates through the whole period is a measurement rather than an argument. What would turn it into one is an induction on the option sets, which is the same missing step the defect reading has.

The convention, named #

Normal play throughout: the player who cannot move loses.

A hexadecimal code .d₁d₂d₃ describes a take-and-break game. Digit $d_k$ says what may be done when $k$ counters are taken: bit 1 that the heap may be emptied, bit 2 that one heap may be left, bit 4 that two may be left, bit 8 that three may be left. So $2$ is take $k$, leave one heap, $6$ is leave one heap or two, and $9$ is empty the heap or leave three.

A sequence is arithmetic-periodic with period $p$ and saltus $s$ when $G(n + p) = G(n) + s$ for every $n$ past some point. Every code here has period nine and saltus three, which is what made them a class.

The plain counter is the period $0\,1\,2\,0\,1\,2\,0\,1\,2$ and the swapped counter is $1\,0\,2\,1\,0\,2\,1\,0\,2$. A period differs from a counter at a place when its value there is not the counter’s.

A family is a set of codes with the same Grundy sequence. The rung below keyed a family on a code’s first sixty values; this page keys it on four hundred, which is what changes the count from four to three.

Where the ladder goes next #

The hexadecimal anchor has five rungs: a period with a constant added, the third digit, the code that climbs by three, the only way to split into three, and now what the class is a perturbation of.

The rung above is the second block. .129 is the only code in the class whose period takes two blocks to settle, and a pre-period is a much rarer thing in this family than a defect — every other code here is arithmetic from its first heap. What makes .129 slow is presumably that its take-one digit is 1 and its take-two is 2, so a heap of one and a heap of two behave unlike every other member’s, and the sequence needs a block to forget them. Checking that against a wider sweep — how many hexadecimal codes with an eventual period have a pre-period at all, and what their small heaps look like — would say whether a pre-period is a fact about small heaps or about something else.

Two neighbours are worth the trip. The third digit is where the odd saltuses were found, and it is the sweep this whole class comes out of. And a period with a constant added is where arithmetic periodicity arrives, and it is the reason a defect in a nine-term period is a defect in an infinite sequence. The code that climbs by three is the single two-digit code with this behaviour, and it is what the whole class is a widening of.