The third take is the other two

Two takes, one line wrote the Grundy sequence of every subtraction game with two legal takes as one sentence: cut a heap’s remainder modulo a + b into blocks of a, alternate nought and one, and turn the even blocks at or past b into twos. It proved the sentence in three cases and then added a third take, and the sentence did not survive. What survived was a reading: the period of a three-take game is a sum of two of its takes six times in seven, and which sum is decided by where the third take falls against the first two’s period, read like a ruler.

The ruler has one mark it cannot read. A third take of exactly a + b lands on the end of the period, and the long irregular periods of the whole three-take census clustered there: the longest, 162, belongs to {6, 13, 19}, and the six longest all had a third take equal to the sum of the other two. The essay ended by asking whether that family has a sentence of its own — a formula for the period in terms of a and b — or whether a take that repeats the other two’s combined reach is where the family’s arithmetic stops having one.

It has one, and the formula says something about the family that no single period would.

The formula #

Take a < b. If a and b share a factor d, the game {a, b, a + b} is the game {a/d, b/d, (a + b)/d} played in units of d: every heap’s value is the value of its quotient by d, repeated d times, and the period is d times the reduced one. So divide out the factor and assume a and b coprime. Write r for the remainder of b on division by 2a. Then the period is

$$p(a, b) = \begin{cases} a(2b + r) & \text{if } 0 < r \le a \quad \text{(the long case)} \\ a\lceil b/a \rceil + b & \text{otherwise} \quad \text{(the short case)} \end{cases}$$

where $a\lceil b/a \rceil$ in the short case is the first multiple of a at or past b.

There is never a preperiod: the sequence repeats from heap nought. Checked against the exact period of the mex recursion on every pair to 80, the formula is right 3,160 times out of 3,160. Of those pairs 1,195 share a factor, 1,362 coprime pairs fall in the short case and 603 in the long. The longest period is {39, 80, 119}'s, 6,318; the 162 that ended the earlier census is {6, 13, 19}, which is long — 13 leaves a remainder of 1 on division by 12 — and 6 × (26 + 1) is 162.

The condition on r has a reading in the game itself. In the game where only a may be taken, the values are blocks of a alternating nought and one, so a heap is a loss exactly when it lies in an even block. r lies between 1 and a exactly when b − 1 does — that is, when the heap one short of the middle take would be a loss in the one-take game. That is the whole of the case distinction: the long case is the pairs for which b − 1 is a losing heap of {a}. It does not involve a + b at all, which is the first sign that the period of a two-take game, a + b, is not the ruler this family is measured against.

Where the one-take game is first disturbed #

The rule about b − 1 is not only a summary of the census; it is visible in the first few heaps of every game, and it explains why the two cases look so different.

Below heap b only the take of a is legal, so the sequence starts as the one-take game {a} — blocks of a alternating nought and one, the pattern take one, three or four opens with and the mex produces when a heap has a single option. Heap b is the first with a second option, the empty heap, worth nought. If b − 1 is a loss of {a}, then b sits inside a block of noughts, its option by a is worth one, and with options worth one and nought the heap is worth two — a two arriving in the middle of a nought block, which is exactly the event that, in the two-take game, closes a period. Here it does not close anything: the take of a + b reaches back across it, the blocks downstream are knocked out of line, and the long case is what that disturbance does to the rest of the sequence.

If b − 1 is a win of {a}, heap b sits in a block of ones; its option by a is worth nought, its option by b is worth nought, and the heap is worth one — the value it would have had anyway. The second take arrives and changes nothing. Nor does anything change until the block ends, at the first multiple of a past b, where a heap that the one-take game would make nought has options worth one and, through the new takes, nought, and so becomes two. That heap is m, the start of the second band. So the short case is short because the new takes are absorbed for a whole block before they act, and when they act they act at a block boundary, where the bands stay aligned.

Computed rather than argued, it holds without exception: over every coprime pair with a at least two and b up to 80, 1,886 of them, the sequence follows the one-take blocks exactly until heap b in the long case and exactly until heap m in the short case, and departs there. The argument above is the reason for the first departure; what follows it in the long case is the part no sentence here describes. It is the same shape of reasoning two takes, one line used to place its single two, and the same habit a period is a proof describes: find the first heap where the obvious pattern could fail and ask what its options are worth.

Two bands of blocks #

The short case is more than a period. Its whole sequence fits in a sentence.

Let m be the first multiple of a at or past b. For a heap with remainder x modulo m + b: if x is below m, the value is ⌊x/a⌋ mod 2 — blocks of a alternating nought and one, the two-take pattern without its two; if x is at least m, the value is two plus ⌊(x − m)/a⌋ mod 2 — blocks of a alternating two and three, a second band exactly b heaps wide. That is all of it. For takes of 3, 10 and 13 it reads 000 111 000 111 222 333 222 3, and the period is 12 + 10.

The sentence is a sentence about blocks of the smallest take, as the two-take sentence was, and its novelty is the second band. The two-take game has values nought, one and two, and its two occupies a single block; here the twos and threes fill a band as wide as the middle take, and the period grows by exactly that band.

For one pair the sentence is proved by the same induction as the two-take sentence. A sequence that repeats with period P and satisfies the mex rule at every heap from nought to P + a + b satisfies it at every heap, because from then on every heap and all three of its options are copies of heaps already checked. Run on each pair in the short case to 80, coprime or scaled, the check closes 2,202 times out of 2,202. That is a proof for each of those games, not for the family: no argument here covers every short pair at once, although the cases it would need — a heap in the lower band, in the upper band, and near the joins — are visibly the same three or four every time.

Seven short games side by side #

The bands are easiest to believe when several games are set beside each other at the same scale.

The rows differ in every number and agree in their shape. {3, 4, 7} is two blocks of three, a block of twos and a single three — the mark at 6, the band four wide. {4, 13, 17} is four blocks alternating nought and one, up to 16, and then thirteen heaps alternating twos and threes in fours. {1, 4, 5} is the degenerate case: blocks one heap long, so the lower band is 0101 and the upper is 2323, and the period is 8. Every pair with a equal to 1 and b even is like that, period 2b; every pair with a equal to 1 and b odd is in the long case, period 2b + 1, because the heap one short of an odd b is even and so a loss when only single counters may be taken.

What none of the rows has is the two-take game’s two. In {3, 8}, the even block reaching past 8 holds a two, and the period is 11; in {3, 8, 11} the period is 54 and the game is long. In the short case the two-take pattern’s single two has been replaced by an entire band.

The long case #

When b − 1 is a losing heap of {a}, the period is no longer a band or two of blocks; it is a times 2b + r, which is roughly the product of the two smaller takes doubled.

The rows are drawn at length 2b + r because that is the unit the period is made of, and the picture shows why the multiplier is a. Each row has blocks of a — runs of three in the first game, of four in the second — but the runs do not line up from row to row: they start at different places, are cut short at different places, and carry their noughts, ones, twos and threes in different orders. The sequence comes back to its first row only after a rows, which is what a misalignment advancing by r each row would need to go all the way round a block of the smallest take, since r and a have no common factor.

That is a description of the picture, not a rule for the values. No sentence here gives the value of a heap in the long case the way the short case’s sentence does, and the rows of {4, 9, 13} show why one is not obvious: the fourth row looks nearly like the short case’s two bands, and the first three do not. The period formula holds on all 603 coprime long pairs to 80, and so does the absence of a preperiod and the bound of three on the values, but in the long case those are measurements and the sequence itself is only computed.

Stripes of width a #

The case a pair falls in can be drawn for every pair at once.

Along a row the pattern repeats every 2a, which is the length of one nought block and one one block of the game {a}. The long stripe is a wide and starts one past each multiple of 2a; the short stripe fills the rest; pairs sharing a factor punch holes in both. Two consequences are visible without any arithmetic. Over a long enough run of b, the coprime pairs split evenly between the two cases, because the stripes are equally wide and a common factor removes the same remainders from each — and when b is less than 2a, r is b itself, more than a, and every pair is short, which is why the census to 80, where many pairs have b below 2a, holds 603 long pairs against 1,362 short. And the case is fixed by b’s remainder modulo 2a alone: neither a + b nor the two-take period of the pair appears in the rule.

That last point is the answer to the question the earlier essay asked in the form it asked it. It read the third take through its remainder modulo a + b — the ruler of the two-take game — and that reading worked for six three-take games in seven. When the third take is a + b the ruler gives nought for every pair and says nothing; the formula shows why. The arithmetic of this family is not a function of a + b at all. It is a function of where b falls against blocks of a, the structure of the one-take game {a} that sits underneath the two-take game, and the third take has made that layer visible by cancelling the layer above it.

A little longer, or ten times longer #

Fixing the smallest take and walking the middle one shows the two cases as two different kinds of growth.

With takes 5 and 16 the period is 21; add 21 as a third take and it is 36, the first multiple of 5 past 16 plus 16. With takes 5 and 21 the period is 26; add 26 and it is 215. Between 16 and 21 nothing about the game looks different — two takes, then their sum — and the period jumps by a factor of six because 20 is a multiple of 10 and so 21 − 1 is a losing heap when only fives may be taken. The scaled pairs follow their reduced forms: {5, 15, 20} is {1, 3, 4} in units of five, period 7 × 5, and {5, 10, 15} is {1, 2, 3} in units of five, period 4 × 5.

The growth is linear in b within each case, slope 2 or so in the short case and slope 2a in the long. So the period of {a, b, a + b} is never larger than about $2ab + a^2$, a quadratic in the takes where the general guarantee for subtraction games — that the sequence is eventually periodic — offers a bound that the period is small and the proof does not say so found to be wildly larger than anything that occurs. Here the gap closes completely, because the period is not bounded but known.

Where this sits among the subtraction games #

The family was introduced with the theorem that every subtraction game’s sequence is eventually periodic, which is the octal games’ guarantee for the simplest codes. The two-take sentence then made one row of the family exact, and this formula makes a second row exact, the one whose third take was the hardest to read. It is not the general three-take game. Most three-take sets are still without a formula — their periods are sums of two takes most of the time, but the values within a period are computed, not stated — and a function with no formula is the reminder that some impartial games’ sequences have resisted every attempt at one.

The connection worth carrying away is the layering. A subtraction game’s sequence is built from the game with fewer takes: {a} gives blocks of a; {a, b} keeps the blocks and adds a two where an even block runs past b; {a, b, a + b} keeps the blocks again, and whether it adds a band or multiplies the period depends on whether b − 1 is a loss in {a}, two layers down. That is the same structure Grundy sequences shows from the outside — every value is a mex over a short look-back — but read along the family rather than along one heap, and it suggests that the next take added to a solved set is read through the solved set’s own losing positions.

The ranges and conventions #

A subtraction game here is a single heap and a set of legal takes; a move removes one of the listed amounts; the player who cannot move loses, so every value is a Grundy value under normal play. Every pair a < b ≤ 80 is included, the third take always a + b. Each sequence is computed by the mex rule to at least four times its expected period plus eight times the largest take, and its exact period is the smallest p for which the sequence repeats with period p over at least three periods, with the smallest preperiod for that p. The short case’s sentence is checked at every heap of every computed sequence, and its induction is run on the reduced pair. Common factors are divided out before the case is decided; “coprime” means a and b share no factor.

What eighty is not #

The formula is not proved for the family. It is exact on 3,160 pairs and on every heap computed; the short case is proved one pair at a time by an induction that closes on each of 2,202 pairs, which is a proof for those games and not for every pair there is.

The long case has no sentence for its values. Its period, its lack of a preperiod and its largest value are measured; what each heap is worth is computed and drawn, not stated.

Nothing here is about three takes in general. The formula belongs to the one arrangement where the third take is the other two added, and the census of all three-take sets to 20 in the earlier essay remains the account of the rest.

Still open: a sentence for the long case #

The long case’s rows are blocks of a that do not line up, and the period says they realign after exactly a rows of 2b + r. A sentence for its values would say where each row’s blocks start and which of the four values each carries, and the fourth row of {4, 9, 13}, which nearly repeats the short case’s two bands, suggests that each row is the short case’s pattern shifted and cut — a pattern with an offset that advances by r, or by some function of it, from row to row. The measurement that would settle it is the offset itself: for each long pair, align each row against the short-case sentence for the same a and b and record the shift that matches it best, and how many heaps the best shift still gets wrong. If the shift is r times the row number and the residue is nought, the long case has a sentence one clause longer than the short case’s; if not, this family has one half with a formula for every value and one half with a formula only for its length.