The only way to split into three

The third digit swept all 4,095 three-digit hexadecimal codes and found 21 whose saltus is not a power of two, against the two-digit sweep’s single exception. It closed on them:

The rung above is the class the twenty-one odd codes make. Nineteen of them climb by three with a period of nine, which is a strong enough coincidence to have a reason: a period three times the saltus is what a sequence counting in base three does … Whether all nineteen share the form, and what the digits they have in common are, is a question with data in hand and no work done on it.

Both halves have answers, and they go opposite ways.

The digits, exactly #

Take the nineteen codes and look at the digit that says what a take of three counters may do. It is 8 or 9 on every one of the eighteen with a period of nine, and nothing else. A digit of 8 is the binary 1000: the take may leave three heaps and may leave nothing else. A digit of 9 is 1001: the take may leave three heaps, or take the whole heap away.

And on all eighteen the other two digits are below 8, so neither the one-take nor the two-take may leave three heaps.

Put in words rather than in digits, the eighteen codes are exactly the ones where the only way to split a heap into three is by taking exactly three counters, and taking three counters can do nothing else. That is a statement about the rules of a game and not about the notation, and it is what the rung below was asking for.

The nineteenth is ·3f0, whose third digit is nought — a take of three is not a legal move at all — and whose period is six rather than nine. It was already the rung below’s exception and it arrives here as an exception to the exception.

And nowhere near enough #

The condition is necessary and it is not close to sufficient. A hundred and twenty-eight of the 4,095 codes satisfy all three clauses, and eighteen of them climb by three: seven codes in eight that look identical under the condition do something else — repeat exactly, climb by a power of two, or fail to settle inside the sweep at all.

That is the ordinary state of the octal and hexadecimal families and it is worth saying rather than apologising for. Naming a game with a number sets out what a code is: a compact statement of the move rule and nothing more. What the sequence does is a fact about the whole recursion, and the survey tradition this ladder is arguing with has never had a route from one to the other. A necessary condition on the digits is about as much as anybody gets.

The form is not shared #

The other half of the rung below’s question comes out negative, and it comes out negative twice over.

Most of the class is aliases. The eighteen codes carry only four distinct Grundy sequences: eight of them give one sequence, six another, three a third, and ·129 is alone. So the class is not eighteen games behaving alike; it is four games written eighteen ways, which is a much weaker coincidence than the count suggested.

And the four sequences are four different shapes. Every one has a period of nine and a saltus of three — that is what put them in the class — and the nine-term periods are 0 1 2 0 1 2 3 1 2, 0 1 2 0 1 2 0 1 2, 1 0 2 1 0 2 1 3 2 and 1 0 2 1 0 0 1 3 2. Only the second of those is what the rung below predicted.

The one that does count in base three #

·209 and five others have the period 0 1 2 0 1 2 0 1 2, which is a counter in base three set down three times, and the whole sequence has the closed form

$$G(n) = 3\left\lfloor \frac{n-1}{9} \right\rfloor + ((n-1) \bmod 3),$$

checked against the recursion on every heap to two hundred. That is precisely the reading the rung below offered from the arithmetic alone: a period three times the saltus is what a sequence counting in base three does.

So the prediction was right about a third of the class and wrong about the rest, which is the most common outcome on this site and is worth taking at face value. The reasoning behind it — that a period of nine with a saltus of three suggests base three — is a constraint rather than a determination: it says the sequence gains three every nine heaps, and it does not say the nine heaps are spent counting.

The three sequences that are not counters are the interesting residue. 1 0 2 1 0 2 1 3 2 is a permuted counter with one term out of place; 0 1 2 0 1 2 3 1 2 is a counter with a 3 where a 0 should be. Each is a base-three counter with a single defect, and whether that is a coincidence of small numbers or a description is the thing the rung above would want.

Why the third digit should matter #

The condition has a mechanism behind it, and although this page does not prove anything, the mechanism is worth setting out because it says where to look next.

A saltus is something the splitting moves buy. The third digit established that on sixteen times the population: not one code without a leave-three bit climbs at all, which is asserted in the sweep rather than observed. Splitting into three heaps is what a hexadecimal code adds to an octal one, and it is what makes the Grundy values grow without repeating.

Now the two clauses of the condition. Only the three-take may split into three means the growth has exactly one source: whatever the sequence gains, it gains from one move rule. And the three-take may do nothing else means that source is uncontaminated — a digit of 8 or 9 offers the splitting move and at most the whole-heap move beside it, so there is nothing to interfere with whatever pattern the splitting sets up.

A single uncontaminated source of growth is the natural condition for a small saltus, and three is the smallest saltus that is not a power of two. So the condition is doing what it looks like it is doing: it isolates the mechanism. What it cannot do is predict the sequence, and the hundred and ten codes that satisfy it and behave otherwise are the evidence for that.

What a class of codes is worth knowing #

The two findings pull against each other and the honest summary is worth stating carefully.

As a class of codes the eighteen are real: one condition on the digits picks them out of 4,095, the condition is about the game rather than the notation, and it is stated in a sentence. Anybody looking for more codes with a saltus of three now knows where to look — among the 110 that satisfy the condition and do not climb, or among the four-digit codes satisfying its analogue.

As a class of games they are four, and the four are not much alike. So nineteen codes that climb by three was a count of names rather than of behaviours, and the class shrinks by a factor of four the moment the sequences are compared instead of the codes.

That distinction has bitten this site before under a different name. The heap is not the position is the same warning one level down — two positions that look alike in the notation and are different games — and this is the same thing at the level of rulesets. A code is a name for a rule, and two rules can be the same game. Nothing in the survey tradition dedupes by sequence, so every count of codes in this literature is a count of names.

The digits that never appear #

There is one more pattern in the eighteen and it is left as an observation rather than a finding, because nothing here explains it.

Among the eighteen, the first digit takes only the values 1, 2, 3 and 6, and the second only 0, 1, 2, 3 and 6. The values 4, 5 and 7 never appear in either position — and 4 is 0100, leave two heaps and nothing else; 5 is 0101, leave two heaps or take the whole one; 7 is 0111, anything but leave three.

So the missing digits are exactly the ones whose two bit is set without the one bit, plus the one with both. Every digit that does appear either has the one bit without the two — 2 and 3 — or has both — 6 — or has neither — 0 and 1.

That is the kind of pattern that is either a real constraint or an artefact of eighteen samples, and eighteen samples spread over eleven distinct digit pairs is not many. What would decide it is the four-digit family, where the analogous class would be much larger; and the third digit already records what a four-digit sweep costs — 65,535 codes and about an hour — which is why it is named here and not run.

What this does not say #

The four sequences are compared over sixty heaps. Two codes count as carrying the same sequence when their Grundy values agree on the first sixty, which is nearly seven periods and is enough for the arithmetic period to have established itself twice over. It is not a proof of identity, and a pair diverging at heap sixty-one would split one of the four families in two.

A window of 160 heaps. Every period and saltus here is found by search inside the rung below’s window, and an arithmetic period found in a window is evidence rather than proof. The base-three closed form is checked to 200 heaps and no further, and the octal survey’s oldest open problems are sequences that looked settled for a very long time.

Four sequences, not four games. Two codes carrying the same Grundy sequence to sixty heaps might diverge later; the comparison is over the window like everything else. What would settle it is a proof that two codes define the same game, which is a statement about the move rules and is available for some of these pairs by inspection and not for all.

The condition was found by looking. It is a pattern read off eighteen codes and then checked against all 4,095, not derived from anything. It could be sharpened — the first two digits take only the values 1, 2, 3 and 6 among the eighteen, and 0, 4, 5 and 7 never appear — and this page has not asked why.

And the exception is one code. ·3f0 breaks the condition, the period and the shape, and one exception is not a second class. It is where the ladder’s third rung started, and its relation to the eighteen is that they climb by the same amount.

Necessary, and nowhere near sufficient #

The digit condition holds on eighteen of the nineteen and is satisfied by a hundred and twenty-eight codes, and the gap between those two numbers is the finding rather than a caveat.

A necessary condition picks out a superset. It says where to look and it does not say what will be found there. A hundred and twenty-eight codes satisfy this one and eighteen of them climb by three, so knowing a code satisfies it raises the odds from one in two hundred to one in seven — real information, and not a characterisation.

What would make it sufficient is a further condition nobody has, and the shape of the shortfall says something about why. The digits describe what a move may do; whether the Grundy sequence climbs by three depends on how those moves interact across all heap sizes, which is a fact about the whole sequence rather than about any single move.

So a rule-table condition can rarely be sufficient in this family, and this is the ordinary situation rather than a local failure. Kayles is $\\cdot 77$ and has no formula, Lasker’s Nim has one, and nothing about the digits says which is which — the same complaint, one level up.

The useful reading is therefore about search rather than about classification. The condition is a filter for a sweep: it reduces 4,095 codes to 128 that are worth computing, which is a factor of thirty in the cost of finding the next member of the class. That is what a necessary condition is good for, and describing it as a characterisation would be claiming the thing it explicitly is not.

What the class is for #

A class of eighteen codes is not, on its own, a reason to care, so it is worth being explicit about what having it buys.

It buys a search. The three-digit family is 4,095 codes and the sweep settles half of them; the four-digit family is 65,535 and a sweep of it is an hour rather than seconds. A condition that is necessary for a saltus of three cuts the four-digit search for that behaviour by a factor of thirty or so before a single sequence is computed — which is the difference between a question somebody runs and one somebody names in a closing paragraph.

It buys a place to look for a theorem. Eighteen codes, four sequences, one closed form and three near-misses is the shape a small piece of theory has just before somebody writes it down. Nothing in the octal survey tradition proves a saltus for a whole family of codes; a proof for these would be the first, and the condition is what the hypothesis of such a theorem would look like.

And it buys a correction to a count. Nineteen codes climbing by three sounded like nineteen games; it is four. Any future census of this family that counts codes rather than sequences will overstate by about the same factor, and knowing that is worth more than the eighteen.

The convention, named #

Normal play throughout: a player who cannot move loses.

A hexadecimal code ·d₁d₂d₃… says what a player may do when removing $k$ counters from a heap, in four bits of the digit $d_k$: take the whole heap, leave one heap, leave two, leave three. An octal code is the same notation with the fourth bit always clear.

A Grundy sequence is arithmetically periodic with period $p$ and saltus $s$ when $G(n + p) = G(n) + s$ from some point on. A saltus of nought is ordinary periodicity; the values then repeat rather than climbing.

A saltus is odd here in the sense of unusual rather than of parity: not a power of two. Every code in the two-digit family with an arithmetic period has a saltus that is a power of two but one, which is what made the 21 worth a page.

Two codes carry the same sequence when their Grundy values agree on every heap in the window. That is what aliases means above, and it is a statement about the window rather than about the games.

Where the ladder goes next #

The hexadecimal anchor has four rungs: that the wider family repeats in a way the octal survey was not written to find, what the constant it repeats with can be, how common that behaviour is, and now what the codes with the least common constant have in common.

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 — so the class is not four unrelated shapes but one shape and three perturbations of it. 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. If it is predictable, the whole class has one closed form with a correction, which is more than the anchor has ever had.

Two neighbours are worth the trip. The code that climbs by three is where the first odd saltus was found and where its closed form was written down, and it is the page whose exception this class turns out to surround. And naming a game with a number is where the notation is introduced, and reading it beside this page shows exactly how much a code says about a sequence — a necessary condition on eighteen codes out of a hundred and twenty-eight, and nothing more.