The sequence nobody has settled

Richard Guy and Cedric Smith wrote down the octal notation in 1956, computed Grundy sequences by hand for dozens of codes, and conjectured that every finite octal game is eventually periodic.

Some of them settle. This one does not.

What the conjecture is claiming #

For a subtraction game — a move takes a stated number of counters and never splits the heap — eventual periodicity is a theorem, and the proof is a counting argument in three lines. The value of a heap depends on the last $m$ values, where $m$ is the largest move; those values are bounded; so the computation has finitely many states, must revisit one, and repeats from there.

An octal game breaks that argument at the first step. A move may split a heap into two, and the value of the split is the nim-sum of the two parts — so the value of heap $n$ depends not on the last few values but on exclusive-ors of pairs drawn from everywhere below it. The computation’s state is the entire history, the state space is not finite, and the counting argument has nothing to count.

So the conjecture is a guess that the conclusion survives even though the proof does not. That is a perfectly reasonable thing to guess, and it has been open since it was made.

Why splitting is the whole difficulty #

It is worth being concrete about what the splitting move does to the dependency structure, because “the state space is not finite” is a sentence that hides the mechanism.

In a subtraction game the value of heap $n$ is the mex of $g(n-t)$ for each allowed $t$. Every term is a single earlier value, and the largest $t$ bounds how far back the computation looks.

In an octal game the value of heap $n$ includes, for each splitting move, terms of the form $g(a) \oplus g(n - k - a)$ for every way of splitting the remainder. So heap 100 depends on the exclusive-or of roughly fifty pairs of values drawn from the whole range below it, and heap 101 depends on a different fifty pairs.

That is why no finite summary is known. A summary would have to determine all those exclusive-ors, and the values feeding them are spread across the entire history rather than concentrated at the end of it.

Which ones settled, and how late #

The survey above computes each sequence to heap 1,200 and asks for a period. The answers spread out in a way that is worth reading carefully.

·137 — Dawson’s chess. Period 34, from heap 52, with five exceptions. Its own essay is about what “eventually” is doing in that sentence.

·07 — Dawson’s Kayles. Period 34 from heap 53, six exceptions. One bit away from ·137 and settling almost identically.

·77 — Kayles. Period 12, but not until heap 71, with sixteen exceptions. Later, shorter period, more exceptions: nothing about the code predicts any of the three.

·6, ·007 and ·106. No period in 1,200 values.

The spread is the point. If lateness of settling correlated with anything visible — the number of digits, the number of set bits, the size of the largest move — the conjecture would have a route to a proof. It does not.

Two heaps of evidence that point different ways #

The conjecture has been tested in two quite different ways, and it is worth separating them because they are usually run together.

Depth. Individual codes computed enormously far. This is the kind of evidence that accumulates without changing shape: ·007 computed to a million values is the same sort of fact as ·007 computed to a thousand, only more so.

Breadth. Many codes computed moderately far, which is what Guy and Smith did by hand and what the survey above does in miniature. Breadth is the evidence that produced the conjecture in the first place — dozens of codes, and every one that settled at all settled with a small period.

The two disagree about how encouraging the situation is. Breadth is encouraging: the settled codes have periods in the tens, not the millions, so the phenomenon looks tame. Depth is discouraging: if the tame ones settle by heap 71, a code that has not settled by heap a million is behaving unlike every settled example rather than like a slow one.

Nobody knows which reading is right, and that is the honest summary. A code could settle at heap $10^{12}$ with period $10^{9}$ and be perfectly consistent with the conjecture and with everything observed.

What an absent counterexample is worth #

This is the part that deserves care, because the temptation to overstate is strong in both directions.

A sequence with no period found in 1,200 values is not evidence of aperiodicity. Kayles has no period in its first 70 values either, and Kayles has a period. Every settled game in the survey looked exactly like an unsettled one until it did not.

But it is also not nothing. ·007 has been computed vastly further than 1,200 by people with better machines and more patience — into the hundreds of millions of values — with no period found. That is a considerably stronger absence than the one drawn here, and it is still an absence.

And the conjecture cannot be confirmed by any amount of computation. It is universally quantified over all octal codes and all heaps; a computation settles one code up to one bound. The most a computation can ever do for the conjecture is fail to refute it, and the most it can ever do against it would be to find a code that provably never repeats — which would need a proof, not a search.

So the evidential situation is: a claim that has resisted refutation for seventy years by methods that could only ever refute it. That is a genuine reason to believe it and it is not a small caveat.

The surprise: the hard part is not computing far #

A reader might expect the difficulty to be arithmetic — that ·007 is open because nobody can compute enough of it. The reverse is closer to true.

Computing the sequence is easy and fast. What is missing is any way to say something about the sequence that is not a value in it. There is no known invariant of an octal code that predicts its period, no bound on where the period must start, and no partial result of the form “codes with property X are eventually periodic”.

That inversion is unusual in this subject. The complexity field here is mostly about problems whose answers exist and are out of computational reach; this is a problem whose computations are within reach and whose answer is not known to exist.

What “sparse” games did to the picture #

One family did move, and it moved in the unhelpful direction.

Some octal codes have long runs of zero digits — moves of most sizes are simply not allowed — and these are called sparse. They were expected to be easier, on the reasonable ground that fewer moves is less structure to account for.

What was found instead is that several of them have enormous periods: sequences that settle only after millions of values, with periods of comparable size. The conjecture survives those cases; the intuition that periods are small does not.

At the depth this page can compute, that shows up as silence rather than as a large number, and the silence is the honest form of the finding.

This is the pattern that makes the problem awkward. Every time somebody has looked for a bound on where a period must begin, the examples have moved the bound. A conjecture whose supporting examples keep getting stranger is not being confirmed, exactly.

The rule that would settle it, and does not exist #

It is worth stating exactly what a proof would need, because the shape of the gap explains why nobody has one.

For subtraction games the state is the last $m$ values, and the proof is that states recur. For octal games one would want a finite summary of the sequence so far, from which the next value is computable — anything finite would do, and the counting argument would then run unchanged.

No such summary is known. The splitting move makes the next value depend on nim-sums of arbitrary pairs from the whole history, and no bounded quantity has been found that determines them. That is the entire difficulty, and it has not moved in seventy years.

Why it matters beyond the family #

An open problem about heap games with funny codes is easy to file as a curiosity. It is load-bearing for a reason that has nothing to do with octal games specifically.

Periodicity is the only general route from a computation to an infinite claim that this subject has. Everywhere a site like this one states something about every heap, every board size, every $n$, the statement rests either on an argument specific to that game or on a period with a certificate. There is no third mechanism.

So the octal conjecture is a question about how far the one general mechanism reaches, and the answer being unknown means the reach is unknown. That shows up directly in what can and cannot be claimed elsewhere: the Grundy table of Wythoff’s game has no period found either, and the honest statement about it is the same shape as the honest statement here.

Where the model stops #

Every claim on this page about a specific code is bounded by the computation behind it. ·007 has no period in the values computed here, and the figure says 1,200 rather than saying “never” for that reason. Elsewhere on this site the same discipline is applied to bounds versus answers, and it matters more here than almost anywhere, because the whole subject of the essay is what a finite computation licenses.

And “finite octal game” is doing work in the conjecture. A code with infinitely many digits — a move may take any number of counters, with the splitting rules varying — is outside the claim, and there the answer is known to be no.

What the picture cannot show #

The survey figure prints each code’s first two dozen values, and twenty-four values is nowhere near enough to see whether a sequence is settling. That is not a defect of the layout. It is the fact the essay is about: the visible part of these sequences carries no information about the answer, and a figure that appeared to show otherwise would be lying.

Kayles is the demonstration. Its first twenty-four values look exactly like ·007’s — no repetition, small numbers, no visible structure — and one of the two settles at heap 71.

The check that could have failed #

The survey is drawn by a program, and a program that reports “no period found” is indistinguishable from a program with a broken period-finder.

So the figure is built to make that failure visible. It refuses to draw if every code in it settles — because then the open case would be missing and the figure would be making the wrong point — and it refuses to draw if none settles, because that is what a broken search looks like. The contrast is required, and the contrast is the check.

The same discipline is why the settled codes carry their periods and exception counts rather than a tick. A period of 34 from heap 52 is a claim with three numbers in it, each of which could be wrong and none of which could be wrong quietly: Dawson’s essay checks the same code from a different figure with different parameters, and the two agree.

Who found it, and what happened next #

Richard Guy died in 2020 at 103, having worked on this and much else for seventy years. Cedric Smith was one of the four undergraduates who, under the collective name Blanche Descartes, worked on squared squares — a separate and equally stubborn combinatorial problem.

Their 1956 paper is the origin of the octal notation and of the systematic survey, and both are still how the subject is done. Guy returned to the conjecture repeatedly and offered money for a resolution of ·007 specifically.

What did not happen is any progress on the general claim. The list of settled codes has grown, the bounds have grown enormously, and the conjecture is where they left it.

What a computation of this size is evidence for #

Billions of terms with no period found is a striking quantity of arithmetic, and it is worth being exact about which claim it supports, because the natural reading is stronger than the evidence.

It is strong evidence that no short period begins early. A search covering periods up to some length in a window of some size rules out exactly those combinations, and the ruling-out is a proof: a period of that length beginning in that window would have been seen. So the computation converts an open question into a much narrower one — any period this sequence has is long, or begins late, or both.

It is no evidence at all that the sequence is aperiodic. Nothing forbids a game whose values settle after $10^{40}$ terms, and such a game is indistinguishable from an aperiodic one under every computation anybody will ever run. The counting argument that bounds the pre-period for subtraction games does not exist for octal ones, which is exactly the gap that makes this question open rather than merely unresolved.

And it is weak evidence about the conjecture. Every finite octal game is eventually periodic is a claim about all of them, and a single code resisting is compatible with the conjecture being true and with it being false. What would settle it is a proof or a counterexample, and a counterexample is not a computation — it would be an argument that some code’s sequence cannot repeat, which is a different kind of object from any amount of the sequence.

So the honest summary of seventy years of arithmetic is that it has narrowed one branch of a three-way disjunction and left the other two exactly where they were.

A note on what the conjecture would give #

Suppose it were proved tomorrow. What would change?

Not much computationally, at first. A proof that every finite octal game is eventually periodic would not say where any period begins or how long it is, unless the proof were constructive — and the counting argument that works for subtraction games gives a bound so enormous as to be useless even there.

What it would give is a licence. Every octal game would then be known to have a closed form, so a search for one is a search for something known to be there, which is a different activity from a search that might be for nothing. That is exactly the difference the subtraction-game argument already provides in its own family, and it is worth more than it sounds: it turns an open-ended computation into a bounded one, even when the bound is not known.

The other half of Guy and Smith’s contribution #

The conjecture is the famous part of the 1956 paper and it is not the useful part.

What has lasted is the notation and the practice that goes with it: name the family by a code, compute the sequence, look for a period, record the exceptions. That turned a scattering of individually-named puzzles into an enumerable family, and every result since — including every extension of the frontier — is stated in those terms.

The value of a notation is a recurring theme here, and octal codes are the cleanest instance in the impartial half of the subject. Before them, Dawson’s chess and Kayles were two unrelated puzzles from different decades; after them, they are neighbours in a family, differing in one bit, and the fact that they behave almost identically is a fact rather than a coincidence.

Where the ladder goes next #

The first rung of this anchor is what a period certifies — a finite window settling an infinite claim, which is one of the cleanest arguments in the subject. This rung is the same argument’s failure to be available, and what a subject does when its best tool does not apply: it computes, it surveys, and it waits.