Two takes, one line

A subtraction game is a heap of counters and a short list of legal takes; a player removes one of the listed amounts, and whoever cannot move loses. Take one, three or four introduced the family and its guarantee — every such game’s Grundy sequence is eventually periodic — and the period is small and the proof does not say so measured how far the guarantee’s bound sits above the periods that actually occur. That essay drew the sequence for takes of 6 and 7 — six noughts, six ones and a two, period thirteen — and called it a pattern that could not be guessed from the rule.

For two takes it can be guessed, exactly, for every pair there is. The sequence is one sentence of arithmetic, the sentence has a short proof, and the proof explains where the six noughts, six ones and the two come from. What makes the result worth an essay is what happens next: a third take breaks the sentence, and the way it breaks says which parts of the two-take structure were accidents of having two and which survive.

The sentence #

Fix two takes a < b, and write p = a + b. For a heap of n counters, let r be the remainder of n on division by p, and let k be ⌊r / a⌋, the number of the block of length a that r falls in, counting from nought. Then the Grundy value of the heap is

• 2, if k is even and r is at least b;
• k mod 2 — nought on even blocks, one on odd blocks — otherwise.

Read against the figure: for takes 3 and 8 the period is eleven, the remainders 0 to 2 form block nought, 3 to 5 block one, 6 to 8 block two, 9 and 10 block three. The blocks alternate nought and one, except that remainder 8 lies in an even block and is at least b, so it holds a two. That is the whole sequence: 00011100211, repeated for ever.

The same sentence for 6 and 7 gives period thirteen, block nought of six noughts, block one of six ones, and a remainder of 12 that lies in block two, is at least 7, and so holds a two — which is the pattern the earlier essay printed and found unguessable. It is not a coincidence of those two numbers. It is the same line with a = 6.

One consequence can be read straight off the sentence before anything is proved. The only values are nought, one and two, and the two appears exactly when some even block reaches past b within the period. The stretch from b to p − 1 is a long, so it always straddles at most two blocks, and it holds no even block only when it is exactly one odd block — when b is an odd multiple of a. Then there is no two, the sequence is blocks of a alternating nought and one, and its period is 2a rather than a + b. Takes of 1 and 3, or 2 and 6, or 5 and 15, are all of that kind.

Three cases and it is proved #

A sentence that fits the first few hundred values is a conjecture. This one is a theorem, and the proof is the ordinary induction on the heap: assume the formula for every smaller heap, and check that the mex of the two options is what the formula says.

The general argument has the same three cases, and each is a line or two.

Below a. The formula says nought. The option n − a has remainder r + b, which is at least b, so its value is one or two, never nought. The option n − b has remainder r + a, in block one; its value is one whether or not it has reached b, because block one is odd. Neither option is nought, so the mex is nought.

From a up to b. The option n − a is the same remainder one block earlier, still below b, so it carries the parity of block k − 1. The option n − b wraps to r + a, one block later. If k is odd, the earlier block is even and holds a nought, and the later block is even and holds a nought or a two — either way the options contain nought and not one, and the mex is one. If k is even, the earlier block is odd and holds a one, the later block is odd and holds a one, and the mex is nought.

From b up to the end of the period. Now n − b has remainder r − b, which is below a: a nought. The option n − a has remainder r − a, below b, in block k − 1. If k is even that block is odd and holds a one, the options are nought and one, and the mex is two. If k is odd that block holds a nought, the only option value is nought, and the mex is one.

Every case gives the formula’s value, and the heaps below the first period, where one or both options do not exist, go through the same way with the options that are there. That is the whole proof, and it is worth noticing what it does not use: no search, no window of computed values, no appeal to the periodicity theorem. A period is a proof settles one game by finding a window of repeated values; this settles every two-take game at once, including those whose period nobody will ever compute by hand.

The census is not needed for the theorem and is not offered as evidence for it. It is there because a proof written by hand can be wrong in a way a proof checked on 780 cases cannot easily be, and because it confirms the two corollaries with exact counts: the period is a + b unless b is an odd multiple of a, and the sequence has no preperiod at all. The second of those is a real difference from the rest of the family. The earlier sweep found sets that take fourteen or twenty-one values to settle into their pattern; no set of two takes takes even one.

Why the blocks are the size of the smaller take #

The shape of the sentence has a plain reason, and it is the reason the third take will break it.

With two takes, a heap of n has at most two options, so its value is at most two, and it is nought exactly when neither option is nought. The smaller take a dominates the early heaps: the first a heaps have no move at all and are noughts; the next a can only take a, landing on a nought, so they are ones; the next a can only take a, landing on a one, so they are noughts again. The alternation in blocks of a is what a game with one take looks like, and until the heap reaches b this game is a one-take game.

The larger take enters at b and does one thing: it reaches back into the first block, which is all noughts. A heap whose remainder lies between b and the end of the period can take b and land in that block, so it always has a nought among its options; its other option, through a, lands one block earlier. When that earlier block is odd, the options are a nought and a one and the heap is worth two; when it is even, the only option value is nought and the heap is worth one. That is the only way a two can arise, and it arises once per period, in the even block past b. After a + b heaps the whole configuration of blocks has shifted back into alignment, and the period closes.

So the two-take sequence is a one-take sequence with a single correction per period, and both the size of the blocks and the length of the period are written in the takes directly. A third take can reach back into the sequence at a third distance, and the correction it makes is not confined to one block.

A heap of a million #

The practical difference between a sentence and a sequence shows up the moment the heap is large. The recursion computes a heap’s value by computing every smaller heap first; the sentence computes it with one division.

A heap of a million counters with takes of 3 and 8: a million is 90,909 elevens and one more, so the remainder is 1, which lies in block nought, and the value is nought. A single heap of a million is lost for the player to move, and nothing smaller had to be looked at to know it. The recursion would have filled in a million values to reach the same answer, and a period search would have needed only the first eleven of them — but it would have needed to know that eleven was the period, which is the thing the sentence supplies.

The sentence also plays sums. Every impartial game is a Nim heap, and a position made of several subtraction games side by side is won or lost according to the nim-sum of their values, exactly as Nim itself is. Put the heap of a million beside a heap of a hundred in the game with takes of 6 and 7. That heap’s remainder modulo thirteen is 9, in block one, so its value is one; the nim-sum of nought and one is one, and the player to move wins. The winning move has to make the second heap worth nought, and the sentence names the target straight away: a remainder in block nought, below 6. Taking 6 leaves 94, remainder 3; taking 7 leaves 93, remainder 2. Both win, and the reason both win is visible in the arithmetic — each lands in the first block of the thirteen.

None of that is available for three takes. The period of a three-take game can be found, and once found it answers the same questions with the same division; but finding it is a search, the search has to run past a preperiod that may be long, and the value inside a period is a table, not a sentence. The difference between two takes and three is the difference between a game one can play in one’s head at any size and a game one has to look up.

The third take, set by set #

Every set of three takes up to twenty — 1,140 of them — has an exact period and preperiod that can be found by computing far enough and searching.

The first thing the census shows is that the sentence’s central fact survives. On six sets in seven the period is still the sum of two of the takes, just as it was a + b for every pair. The period of a subtraction game with a few small takes is not some unrelated number that happens to be small; it is usually built from the takes in the simplest way possible.

The second is that the rest of the sentence does not survive. Three options allow the value three, and more than half of the sets reach it. A fifth of the sets have a preperiod — they take some time to settle, in the way the sequence nobody has settled describes for the octal games, where the waiting may never end. And the one-take core that made the blocks is no longer in charge: with three takes, the second take can reach back into the one-take stretch before b is hit, and the corrections interfere.

What the census cannot say by itself is which sum a given set’s period is. a + c for {1, 2, 3} and {1, 2, 6}; a + b for {1, 2, 4} and {1, 2, 5}; b + c for {1, 3, 4}. There is no obvious rule in that list — until the list is laid out the right way.

Read modulo the first two #

The right way is to fix the first two takes and let the third move.

Each row is a pair {2, b} with a third take walking out to the right, and each row is striped with a period in c equal to 2 + b — the period of the pair. For {2, 3}, the classes run a + c, a + c, b + c, a + b, a + b and repeat every five values of c; for {2, 5}, the stripes repeat every seven. The third take is not an independent third parameter. It acts through its remainder modulo the period of the first two, which is to say through its position in the two-take sentence: whether c lands in an even block or an odd one, before or after b, decides which sum the new period is.

That is the sense in which the formula survives the third take. It no longer gives the values, but it still gives the frame: the pair’s period is the ruler against which the third take is measured, and the class of the answer is a function of where on that ruler the third take falls. The repetition is not perfect — 24 cells of 365 break it — and every one of the breaks involves a period that is no sum of two takes. Those are where the frame stops being enough.

The long periods sit on the sum #

The sets whose periods are no sum of takes include the longest periods in the whole census, and they have a common feature that the map already hints at.

The third take equal to the first two added together is the one arrangement in which the third take does nothing new in terms of distance: a take of a + b is a take of a followed by a take of b, performed in one turn. In the two-take game, a + b is the period — the distance at which the whole block structure comes back into alignment. A take of exactly that length jumps from any heap to the heap at the same position in the previous period, which in the two-take game has the same value; so every heap gains an option worth its own two-take value, and the mex rule, which forbids a heap from equalling an option, is forced to break the pattern everywhere at once. The frame is not perturbed at one point per period, as by a generic third take; it is contradicted at every point. What emerges is a period far longer than any of the takes, 162 against 19, and a pattern no sentence of this kind describes.

That fits with the earlier sweep’s worst case. The period of 22 that broke the rule of thumb in that essay belongs to {2, 5, 7} — and 7 is 2 + 5.

The convention, and the range #

Normal play: the player unable to take loses. Heaps are counted from nought, and takes must be exact — a heap smaller than every take is a terminal position. The pair census is every a < b ≤ 40, checked to 1,200 values; the triple census is every a < b < c ≤ 20, each computed to at least 3,000 values and to sixty times its largest take, which is well past every period and preperiod found. The exact period is the smallest p for which the sequence eventually repeats with period p and holds that repetition for at least three full periods of the values computed, and the preperiod is the first heap from which it does.

What the strips cannot show #

The two-take formula is proved above for every pair, not only those counted. The three-take statements are counts on the sets computed and nothing more: that the period is usually a sum of two takes, that the class repeats in c with the pair’s period, and that the longest periods sit on c = a + b are observations on 1,140 sets and on 365 cells of one map, and each could have exceptions beyond them. Why a third take is read modulo the first two’s period is described in terms of the two-take sentence and not proved; no argument here says the stripes must repeat, or where they must start. And the explanation offered for the long periods on the sum is a mechanism, not a theorem: it says why the two-take frame is contradicted everywhere at once, not what replaces it.

Still open: a sentence for the sum #

The map says the third take’s effect depends only on where it falls against the pair’s ruler, with one exception: the point where it falls exactly on the ruler’s end. That makes the sets {a, b, a + b} the family to understand next. Their periods run from the short and ordinary — a sum of takes, on half of them — to 162, and the question is whether they, too, have a sentence: whether the period of {a, b, a + b} is a function of a and b that can be written down, as the two-take period can, or whether the one take that repeats the others’ combined reach is the point at which the family’s arithmetic stops having a formula at all. Grundy sequences is where the family’s other members are drawn, and a function with no formula is what the answer would look like if it is the second.