What the arithmetic cost in 1956

The rung below ends with a sentence of admiration:

The period of ·137 was found in that period, by hand, and has been confirmed by every computation since. There is something worth respecting in that: fifty-two values of a sequence with no visible pattern, computed by a person, far enough to find a repeat of length 34 and to check it.

Respect without a number is a compliment. This rung supplies the number, and the number turns out to say three things the compliment does not: what a certificate costs against what a discovery costs, which bit of an octal code decides the shape of the bill, and which of the games in Guy and Smith’s own survey were out of reach of the method they were using.

The unit has to come from the game #

Pricing a hand computation is easy to do badly. A count of hours needs a rate; a count of “steps” needs a definition; and either invites a reader to argue about the assumption rather than about the result.

So the unit is taken from the arithmetic itself. Computing a Grundy sequence by the mex rule requires exactly two kinds of operation, and both are things a person performs with a pencil:

A mex. For each heap, collect the values of the options and take the least non-negative integer not among them. One per heap, always.

An exclusive-or. For each splitting move, the value of the split is the exclusive-or of the two parts, and that is a separate calculation for every way of splitting.

Both are counted from the same enumeration octalGrundy runs, so the count is the work the computation actually does rather than an estimate of it.

Finding and proving are different bills #

The rung below explains what makes an octal period a theorem rather than an observation, and the explanation has a number in it that is easy to read past.

Finding the period of ·137 means computing far enough to see the repeat, which is heap 52. Fifty-two values.

Proving it means satisfying Guy and Smith’s window: the repeat must hold from the period’s start s all the way to 2s + 2p + m, where p is the period and m is the number of digits in the code. For ·137 that is heap 175, and the certificate is a hundred and twenty-four values rather than three.

Those two are not the same computation with a different stopping point. Priced properly they are:

Finding: 754 operations. Proving: 7,919.

More than ten to one. The discovery is a morning; the proof is a fortnight, and the fortnight is the part that makes the result true rather than probable.

That ratio is the honest content of a period is a proof, and it is not a fact about ·137. It is a fact about the window, which is quadratic in the start, and the start is where a hard sequence spends most of its length.

The bit that decides the shape of the bill #

Read down the table and one column separates the cheap games from the expensive ones, and it is not the period and not the number of digits.

It is the fourth bit.

An octal digit is read in binary: the 1-bit says a move taking k counters may empty the heap, the 2-bit says it may leave one heap, and the 4-bit says it may split the remainder in two. With the 4-bit off, a heap’s value is a mex over a fixed number of values below it, and computing to heap n costs work proportional to n.

With the 4-bit on, the value of a heap is a mex over exclusive-ors of pairs from anywhere below it, and there are about n/2 such pairs at heap n. So the work to reach heap n is proportional to n², and every splitting code pays it.

·137’s third digit is a 7, which is 1 + 2 + 4. The bit is on, and it is on for the reason the rung below gives: the splitting move is what makes ·137 an octal game rather than a subtraction game, and it is what makes the whole family interesting.

So the difficulty and the interest arrive together, from the same bit. A code with no splitting is cheap to compute, cheap to certify, and is a subtraction game whose theory the rung below calls a short proof. A code with splitting is quadratic, needs a window a hundred and twenty-four values long, and is where every open problem in the family lives. It is also what makes a position a collection of rows rather than a heap, so that the last step of evaluating one is a nim-sum over however many parts the splitting has produced.

What one heap costs, as the heap grows #

The totals hide a shape and the shape is the argument, so it is worth reading the per-heap cost rather than the sum.

At heap 10 of ·137 the enumeration offers a handful of options: the whole heap for the first digit, one remainder for the second, and four ways to split for the third. At heap 100 the splits alone are fifty. At heap 175 they are eighty-seven.

So the cost of the nth value grows linearly, and the cost of reaching heap n grows as n². Doubling how far the computation goes quadruples the bill.

That is what makes the window expensive rather than merely long. A hundred and seventy-five values is three and a third times fifty-two, and the certificate costs ten and a half times what the discovery does — which is close to the square of the ratio, and it is close for the reason the quadratic gives.

And it is why a person can do it and a person could not do much more. A sequence settling at heap 500 rather than 52 would need a window near heap 1,600 and a bill a hundred times larger, and there is no version of a pencil that survives that. The codes Guy and Smith settled by hand are the codes whose periods start early, and the seventeen that defeated them are not seventeen hard codes so much as seventeen codes whose difficulty is somewhere nobody could reach.

What sixty-four codes cost #

The sweep takes every one- and two-digit code — sixty-four of them, plus ·137 — computes the sequence to a heap of a thousand, and prices whichever ones settle.

Forty-seven settle and seventeen do not.

Of the forty-seven, the costliest certificate is ·47 at sixty-three times ·137’s, and ·45 is beside it at the same order. Most of the rest are far cheaper: ·3 and ·5 certify in a couple of dozen operations, ·157 in about a fortieth of a Dawson, ·77 at not quite twice.

So ·137 is not the hard case. It sits near the bottom of the settled codes, and what makes it famous is not that its certificate is expensive but that its sequence looks random for fifty-two values and then does not.

That reframes what Guy and Smith accomplished, and it reframes it upward rather than down. They were not computing the hardest thing in the family; they were computing one of the middling ones, by hand, in a family whose hardest settled member costs sixty-three times as much and whose seventeen unsettled members cost everything anybody has spent on them and have returned nothing.

The seventeen with no price #

The unsettled codes are the interesting column and they are quoted as unsettled rather than given a number, because a certificate that does not exist has no cost.

·6, ·04, ·06, ·14, ·16, ·36, ·37, ·56, ·61 through ·67, ·74, ·76 — seventeen of sixty-four, computed to a heap of a thousand with no period found. ·007 and its neighbours have been pushed vastly further by machine and have returned nothing either, and the conjecture that every octal game’s sequence must eventually settle is seventy years old and open. A period is a proof only where there is a period, and nothing distinguishes a code that has one from a code that does not.

For those codes the pricing question is not “how much would a certificate cost” but “is there one”. A reader could compute for ever and never know whether the next value is the one that starts the repeat, and no amount of arithmetic distinguishes has not settled yet from never will.

That is the sharpest thing the pricing says about the method. A cost is a statement about a computation that terminates. Seventeen of sixty-four codes are outside the reach of any cost, and the method Guy and Smith used cannot tell in advance which of the sixty-four it will be.

Why nothing about a code predicts its bill #

The table has the digits in one column and the price in another and there is no relation between them, which is worth stating as a finding rather than leaving as an impression.

·07 and ·137 differ by a whole digit and cost the same. ·77 and ·07 differ in one digit and differ by a factor of two. ·47 and ·46 differ in one bit and one of them costs sixty-three Dawsons while the other costs seven. ·6 and ·5 differ by one and one of them has no certificate at all.

That is the periodicity conjecture’s whole content seen through a different instrument. There is no known map from a code to any property of its sequence — not to the period, not to the start, not to whether one exists — and the pricing adds one more property to the list of things the digits do not determine.

Which is what makes the family a table of computations rather than a theory. A theory would let a reader look at ·47 and know it will be expensive. Nothing does, and the only way to find out what a code costs is to pay.

What the price buys #

The rung below explains what a period is worth in the currency of lookups: without one, the value of a heap of a million costs a million mex computations; with one, it costs a division and a lookup in a table of thirty-four numbers.

Set that beside the certificate’s price and the trade is stark. Seven thousand nine hundred and nineteen operations, once, buys constant-time answers about heaps of any size for ever. That is the transformation a closed form always makes, paid for up front, and it is why periodicity is the property people look for in these sequences rather than any other. What a rule table costs against the answer it determines is the same trade measured in bits rather than in operations.

And it says why the seventeen matter more than a gap in a table. A code with no period found is a code where every answer costs the full linear computation, for every heap anybody asks about, indefinitely. The absence of a certificate is not a missing theorem; it is a permanent bill.

Why the window is so much longer than the repeat #

The window is where the whole factor of ten lives and it is worth saying why a proof needs so much more than a discovery.

A repeat observed over one period is an observation. A repeat over the window is a theorem, because the window is long enough for an induction: once the values from s to 2s + 2p + m all agree with their counterparts a period earlier, every later value is a mex over values that are themselves periodic, and the periodicity propagates for ever.

The reason the window depends on s at all — twice it, in fact — is the splitting move. A heap’s value can depend on the exclusive-or of two parts, and the parts can be anywhere below it, including in the pre-periodic stretch. So the induction has to reach far enough that no split can land a foot in the irregular part, and how far that is depends on how long the irregular part is.

A game with a long pre-period pays for it twice: once in computing the pre-period, and again in the window that has to clear it. ·77’s start of 71 is what makes its certificate expensive despite its short period, and ·47’s start is what makes it the worst in the sweep.

That is the shape a reader should carry into any claim about one of these sequences. The interesting number is not the period. It is where the period starts.

What the picture cannot show #

No hours are estimated anywhere. The operations are counted exactly and the translation into human time is not attempted, because it would need a rate and the rate would be invented. What a reader can do with the numbers is compare — sixty-three times, ten to one, a fortieth — and comparison is what the units are for.

And the count is of a particular way of computing. The enumeration priced here is the one octalGrundy performs, and a person working by hand would take shortcuts a program does not: noticing a value must be nought without checking every option, reusing a split computed a few heaps earlier, spotting a pattern and testing it rather than deriving it. So the count is an upper bound on what Guy and Smith did, and probably a generous one.

Nor does anything here price the search for the period, which is a second pass over the sequence and is the cheap half: for each candidate start and length, check whether the window repeats. That cost is small beside computing the values and is not in the table.

The convention, named #

Normal play, as everywhere in the octal family: the player who cannot move loses. Every value, every period, every window and every price on this page is a statement about that convention.

That deserves saying because the pricing invites a natural question — what would the misère certificate cost — and the answer is that there is no such object. Under misère play a heap does not have a value in the sense that composes, so there is no sequence to find a period in, and the whole apparatus of windows and certificates has nothing to attach to.

So the bill above is not the bill for understanding Dawson’s chess. It is the bill for understanding it under one convention, and the convention is not the one Dawson posed it in — which is the rung above.

The surprise: the cheap half is what everybody quotes #

The result everybody repeats about ·137 is eventually periodic with period thirty-four from heap fifty-two, and those are the numbers of the discovery: fifty-two values, seven hundred and fifty-four operations, the cheap end of the computation.

The theorem is the window, and the window is heap one hundred and seventy-five and 7,919 operations, and nobody quotes it. The rung below already noticed the same thing about the other half of the result — that eventually is the word doing the work in the famous sentence, and that the five exceptions it hides are usually lost — and this is the same loss on the other axis. What computing further has bought asks the same question of a different open problem, and gets the same kind of answer.

A result gets remembered in the form that fits in a sentence, and the form that fits in a sentence is the observation rather than the proof. That is the identical pattern the determinacy anchor records about Zermelo, where the theorem everybody quotes is the corollary and the paper’s substance is a bound nobody repeats. Two results, forty-three years apart, both remembered for their cheap half.

There is a practical version of the moral for anybody reading a claim about one of these sequences. Ask where the period starts, not what it is; ask whether the window was checked, not whether the repeat was seen; and expect the two numbers to be a factor of ten apart, because the window is quadratic in the start and the start is where the difficulty is.

Where the ladder goes next #

dawson now has the game, the exceptions its quoted result loses, and the price of the result nobody quotes.

The rung above is the convention. Dawson published his puzzle in 1934 as a problem in which the loser is the player to run out of moves, and every compact statement on this ladder — nine values, a period of thirty-four, a certificate a hundred and twenty-four values long — is a statement about the other one. Under his own, a heap does not carry a number at all, and what replaces it is an object whose size grows with the heaps in view.