The quantity that carried nothing

A pattern that has not started yet found that a pre-period is the ordinary case rather than a curiosity — 843 of the 2,050 three-digit hexadecimal codes have one — and that the take-one digit predicts whether a code will, at rates running from nought to 78 per cent. It closed by naming the half it had not done, and by naming the two quantities the answer should be built from:

The take-one digit predicts whether there is one; nothing here predicts how long, and the mechanism above says the length ought to be roughly how long the sequence takes to climb past its own small values — which is a quantity computable from the saltus and the period without running the sequence.

One of those two quantities carries the whole of the answer and the other carries none of it.

The saltus is inert. Its correlation with the length is −0.027, and the sign is meaningless at that size. The period’s is 0.768.

Why the saltus was expected to matter #

The mechanism the rung below proposed is a good one and it is worth stating before it is taken apart, because the reason it fails is more interesting than the fact that it does.

A hexadecimal code’s sequence, once it settles, satisfies $G(n + p) = G(n) + s$ for a period $p$ and a saltus $s$: the same block of values repeated, with a constant added each time round. The values therefore grow linearly, at a rate of $s$ per $p$ heaps. The mex that produces each value has to climb past whatever small values the sequence used early on, and a sequence climbing faster should get past them sooner. So a large saltus ought to mean a short pre-period, and the estimator ought to divide by it.

That argument is not wrong about the growth. It is wrong about what the pre-period is. The sequence does not have to climb past its small values; it has to stop being surprised by its options. A pre-period ends when the option set of every heap from there on is the option set the periodic rule predicts, and the option set is decided by the rule table — by which splits are legal and how many heaps a move may leave — rather than by how fast the values are growing. A sequence with a large saltus climbs quickly and can still be finding new option patterns for another forty heaps.

The distinction is invisible while looking at one code and obvious across 843, which is the ordinary reason a mechanism survives being written down.

There is a second reason the saltus was a natural candidate and it is worth dismissing separately, because it is the stronger of the two. The saltus is the quantity that makes these sequences unbounded — a code with saltus nought has an eventually periodic sequence with a finite value set, and one with a positive saltus climbs forever. Since the whole difficulty of a pre-period is the sequence using values it will not use again, a quantity governing how fast it leaves its early values behind ought to matter. It does not, and the 191 codes with saltus nought are the cleanest demonstration: they never climb past anything at all, they have pre-periods, and their pre-periods are the same length as everybody else’s relative to their periods.

That is the sharpest form of the negative result. A quantity is inert not merely on average but on the sub-population where the proposed mechanism predicts the largest effect.

What the period does #

Fitting the length on the period alone gives $\text{pre-period} = 1.06 \times \text{period} - 0.11$, which is, to within the precision the data supports, a pre-period is one period long. The median absolute residual is 1.06 heaps and four codes in five sit within one period of the line.

The constant being indistinguishable from nought is worth as much as the coefficient being one. A fitted line through this data could have come back with a substantial intercept, which would say that settling costs a fixed number of heaps plus a bit per period — a plausible shape, and a different mechanism. It comes back with −0.11 on a quantity that runs from 1 to 70, so there is no fixed cost. The whole of the settling time is proportional, which is what makes the block reading below available at all.

That is a satisfying answer and it becomes a better one when the ratio is looked at directly rather than through a fit.

The median ratio is exactly 1.00. One hundred and forty-two codes have a pre-period of exactly one period, and 325 of the 843 have a pre-period that is an exact multiple of their period.

That last figure is the one worth pausing on, because it is not what a fitted line describes. A quantity that lands on exact multiples of another quantity two-fifths of the time is not merely correlated with it; it is being measured in units of it. The pre-period is not a number of heaps that happens to be near the period — it is a number of blocks, and the block is the period.

The two halves come apart #

The rung below’s strong predictor and this rung’s strong predictor are different quantities, and neither does the other’s job.

The take-one digit decides whether. Digits d and e never produce a pre-period over 144 codes; 9, 1, b and f produce one on more than half. And the length, for every digit that produces one, has a median of two, three or four heaps. Sixteen digits, existence rates spanning the entire range from nought to 78 per cent, and a median length that never leaves a window three heaps wide.

The period decides how long, and says nothing about whether — a code with a period of nine may have no pre-period at all, and 1,207 of the 2,050 settled codes do not.

So the question the rung below asked as one question is two. The digit is a statement about the rule’s behaviour on the smallest heap, and whether a sequence ever gets confused is decided there. The period is a statement about the eventual pattern, and how long the confusion lasts is measured in that pattern’s own units. There is no reason for one quantity to answer both, and it does not.

The last column of that figure adds a third statement, and it is the one a sweep would actually use. Four digits — 6, 8, a and c — never produce a pre-period longer than six heaps across 672 codes, while 3 and 7 reach 67 and 70. The digit is a ceiling and the period is a location. Knowing both is knowing where to expect the pre-period to end and how far it could conceivably run, which is more than either gives alone and is exactly what a sweep needs to choose its depth.

What this is worth to a sweep #

The reason anybody wants a pre-period’s length is that a sweep has to choose a depth, and choosing it wrong is the failure mode this whole class of games specialises in.

A Grundy sequence read to depth $d$ looks periodic from wherever it happens to have settled. If the reading starts inside a pre-period, the sweep reports a period that is not the period, and reports it with complete confidence — there is nothing in a finite window that says this window is too early. A period is a proof is the argument that rescues this: a window long enough to contain two full periods past the settling point certifies the pattern forever, because the recursion cannot see past a window of that length. The certificate is unimpeachable and it has one input, which is where the settling point is.

So the depth a sweep needs is the pre-period plus two periods, and until this page the first term had no estimate at all. The rung below could say whether a code would have a pre-period, from its take-one digit, which tells a sweep which codes to be careful with and not how careful. The estimate here says: budget one period for settling, and know that four digits in sixteen cap it at six heaps while two of them reach seventy.

That is a real saving on a real sweep. Reading every three-digit code to a fixed 160 heaps costs the same on the 1,207 codes that settle immediately as on the eight that need fifty; reading each to its own estimated depth spends the arithmetic where the codes need it. And it is exactly the kind of budgeting that the sequence nobody has settled has never been able to do, because the codes that matter there have no period to measure a pre-period against — the estimate needs a period, and the open codes are open precisely because nobody has one.

The caution the rung below issued survives intact and is sharpened. A family key built from a code’s first $N$ values is a key on a pre-period unless $N$ exceeds it, and the longest pre-period among the two-digit codes is 143. What this page adds is that the risk is not spread evenly: a code whose period is small is very unlikely to need a long key, and the codes that broke the key were the ones with the longest periods and the worst luck.

The eight the line misses #

Eight codes of the 843 have a pre-period at least five times their period, and the fifth of them is ·129.

That is worth stating plainly, because ·129 is where this line of questions began. Two counters and one displaced term found the odd-saltus class carrying three eventual sequences rather than four, and found it because ·129 looked like a family of its own for as long as a family key read a code’s first sixty values — which was almost entirely inside its 54-heap pre-period. The rung below then asked how common that was and found it common. This rung asks how long it usually lasts and finds ·129 one of eight exceptions out of 843.

So the estimate and the case that raised the question are both correct and they are not about each other. A pre-period is about one period long, and the code that made anybody look at pre-periods has one six times that. Two of the eight have a period of one, where a ratio is a division by the smallest available number and means less than it looks; ·1f9 at 15.3 periods and ·3de at 7.4 do not have that excuse.

The narrower family #

The 137 two-digit codes are the only control this family has, and 47 of them have a pre-period. Two of the three findings survive the change. The saltus is inert there as well, at −0.12 — larger than −0.03 and still nothing over 47 codes. And the median ratio is exactly one there too, which is a stronger transfer than the correlation is: it is the same statement about units, arrived at independently.

The fitted coefficient does not transfer. It is 1.06 on the three-digit codes and 1.74 on the two-digit ones. So the sentence a pre-period is about a period long is a good description of the wider family and an underestimate on the narrower one, and the honest form of the finding is the median ratio rather than the fit. A ratio whose median is one on both populations and whose mean differs between them is a ratio with a skewed tail, and the tail is what the least-squares line is chasing.

Who found what, and when #

The hexadecimal family is Conway’s extension of the octal games, and the arithmetic period — a block repeated with a constant added — is the kind of eventual behaviour Guy and Smith’s 1956 survey established as the thing to look for. That the settling point is a separate quantity from the period, and that a sweep has to know both, is old and universally understood; what has never had a number attached is how far apart they usually are.

Everything on this page and the two rungs below it is this site’s own sweeping. The line of questions started by accident, at two counters and one displaced term, where a family key sixty values long turned out to be sitting inside one code’s pre-period and split a class of twenty-one codes into four families instead of three. The repair was to lengthen the key. The interesting part was that nobody could say how much longer it needed to be, and the two rungs since have been the two halves of answering that: how often the problem arises, and how big it is when it does.

The shape of the answer is worth recording separately from the answer. A defect found by accident produced a question about a population, the population turned out to behave quite unlike the case that raised it, and the case that raised it turned out to be a genuine outlier — one of eight in 843. That is the ordinary way this goes and it is worth saying, because the opposite conclusion was available at every step: ·129 looked like a warning about pre-periods in general, and it is a warning about ·129.

What the solver computed, and how #

Every code of two digits and of three, less the game with no moves — 255 and 4,095 of them. Each code’s Grundy sequence is generated to 360 heaps for the two-digit codes and 160 for the three-digit ones by the ordinary octal recursion: the value at heap $n$ is the mex over every legal move, and a hexadecimal digit says how many heaps a move may leave when it takes that many counters.

Each sequence is then handed to an arithmetic-period detector, which looks for the smallest $p$ and $s$ and the smallest starting heap $t$ such that $G(n + p) = G(n) + s$ for every $n \geq t$ inside the window. The pre-period is $t - 1$. Codes whose sequence does not settle inside the window are dropped — 2,045 of the three-digit codes — and every number on this page is over the ones that do.

The correlations are ordinary Pearson coefficients of the pre-period against each candidate, and the fit is least squares of the pre-period on the period. The residual figures are absolute, sorted, and reported at the median and the ninetieth percentile rather than as a variance, because the distribution has a tail of eight and a variance would be a statement about those eight.

Four things are asserted rather than reported. The saltus’s correlation must be under 0.2 in absolute value and the period’s over 0.6, or the page has the two quantities the wrong way round. The fitted coefficient must be within a quarter of one, and the median ratio must be exactly one. And ·129 must be among the codes running five periods or more, since the closing reading is that it never was typical.

Where the model stops #

A window of 160 heaps for the three-digit codes, which is what settles the sweep in an affordable time and is also its principal limitation. A code whose pre-period exceeds 160 is not recorded as having a long pre-period; it is recorded as not settling, and dropped. So every number here is conditioned on the code having settled inside the window, and the tail of the distribution is censored on the right by construction.

That matters for one claim and not for the others. The median ratio and the inertness of the saltus are robust to it — a censored tail cannot move a median that sits at one. The fitted coefficient is not: dropping the codes with the longest pre-periods biases the line downward, and the two-digit codes, swept to 360 heaps, give 1.74. Some of the gap between the two coefficients is the censoring rather than the family.

Normal play throughout, and the arithmetic period is a fact about normal-play Grundy values; misère play has no saltus and nothing on this page applies to it.

And the figures cannot show the thing the mechanism section claims, which is why a pre-period is a whole number of blocks. The tables report that 325 of 843 are exact multiples and that the median ratio is one; they exhibit no argument connecting the period’s block structure to the settling time. That argument is what would turn this page’s estimate into a statement, and nothing here is it.

Where the ladder goes next #

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

The rung above is the block argument. Two-fifths of these codes have a pre-period that is an exact multiple of their own period, and the estimate is that a pre-period is one block long — which together suggest that the settling is a block-by-block process rather than a heap-by-heap one: the sequence either reproduces the whole block correctly or does not, and the pre-period counts failures. Testing that costs nothing new. For each code with a pre-period, ask whether the values inside each pre-period block match the eventual rule at some offset, or at none — a sequence settling block by block should show the last pre-period block agreeing with the pattern nearly everywhere and the one before it agreeing nowhere. If that is what happens, the pre-period is a count and the fit becomes a theorem about counting; if the disagreements are scattered through the pre-period rather than concentrated at its start, the block reading is a coincidence of the multiples and the right unit is something else.

Two neighbours are worth the trip. A period is a proof is where a finite window is shown to settle an infinite claim, and its whole argument depends on knowing where the period starts — which is the quantity this page estimates, so the two together are the site’s account of what a sweep has to know before it can stop. And the third digit is the sweep this class comes out of, and it is worth reading beside a page whose finding is that one of its two headline quantities carries no information at all.