I’ve written here before about subtraction games, two-player games in which the players remove tokens from a pile of tokens, the number of removed tokens is required to belong to a designated subtraction set, and the goal is to make the last move. For instance, subtract a square, a game I studied at FUN 2018, is of this type, with the subtraction set being the square numbers.

At some point in studying these games I also briefly looked at the subtraction game whose subtraction set is the set of practical numbers, the numbers whose sums of divisors include all values up to the given numbers. The sequence of these numbers begins

\[1, 2, 4, 6, 8, 12, 16, 18, 20, 24, 28, 30, 32, 36, \dots\]

and it turns out to be important here that, after the first one, they’re all even. Let’s call the subtraction game with this subtraction set subpract.

For a subtraction game, or more generally any impartial game, the game states can be partitioned into \(\mathcal{P}\)-positions (where the player who played previously is winning with optimal play) and \(\mathcal{N}\)-positions (where the next player to move can force a win); the \(\mathcal{P}\)-positions tend to be rarer than the \(\mathcal{N}\)-positions, and it’s important to know where they are because the optimal strategy in the game is to move to a \(\mathcal{P}\)-position whenever possible.

OEIS A275432 lists the \(\mathcal{P}\)-positions for subpract. They are:

\[0, 3, 10, 13, 44, 47, 102, 105, 146, 149, 232, 235, \dots\]

For instance, it’s a winning move in subpract to move to a pile of ten tokens (if you can), because whatever move your opponent makes from there lets you win. If your opponent takes an even number of tokens, you will be able to take all the remaining tokens and win immediately. And if your opponent takes one token, leaving a pile of nine tokens, you can win by taking six more and leaving a pile of three tokens. Then, regardless of how your opponent responds, you will be able to take all the tokens on your next move.

An obvious pattern jumps out from this list of \(\mathcal{P}\)-positions: they come in pairs, spaced three apart. More precisely, an even number \(2x\) is a \(\mathcal{P}\)-position if and only if the odd number \(2x+3\) is a \(\mathcal{P}\)-position. It’s not just a coincidence, true at the start of the sequence and then false later on: it carries on throughout the entire sequence of \(\mathcal{P}\)-positions. More strongly, this same three-apart pairing of \(\mathcal{P}\)-positions holds for any subtraction game whose subtraction set contains \(1\), \(2\), and \(4\), and does not contain any other odd numbers.

Proof of the pairing property

To prove this, I need to show that \(2x\) is a \(\mathcal{P}\)-position if and only if \(2x+3\) is a winning position. We can prove this by induction, where we assume that all the \(\mathcal{P}\)-positions below \(2x\) and \(2x+3\) are paired up in the same way, and use it to prove that the same pairing holds for \(2x\) and \(2x+3\). The basic idea of the proof is to assume that one of the two players has a winning strategy for the position \(2x\), and to copy that strategy for \(2x+3\), most of the time playing the same moves and responses that you would play for the smaller position. Whenever a sequence of moves is applicable to both \(2x\) and \(2x+3\) and preserves the parity of the starting position, the induction hypothesis shows that it has the same outcome for both starting positions. However, there are a few cases where you may be forced to deviate from this strategy:

If \(2x\) is an \(\mathcal{N}\)-position, but its winning move is to subtract one token leading to an odd \(\mathcal{P}\)-position \(2y+3\), then copying that move from the starting position \(2x+3\) would lead to the position \(2y+6\) which may not be a \(\mathcal{P}\)-position. Instead you should subtract four tokens to get to the position \(2y+3\) directly.
If \(2x\) is a \(\mathcal{P}\)-position, and you’re trying to copy its winning strategy in the position \(2x+3\), your opponent may be able to subtract \(2x+2\), a move that is not possible in \(2x\), so you have no response to copy. But in this case the result is a pile of just one token, from which you can immediately win.
Again, if you’re trying to copy the winning strategy for \(\mathcal{P}\)-position \(2x\) in the position \(2x+3\), your opponent may subtract only one token. In this case, the winning response when starting from \(2x\) might be to subtract an even number, leading to an odd \(\mathcal{P}\)-position \(2y+3\). If you copy this response, you will end up at \(2y+6\) which may not be a \(\mathcal{P}\)-position. But instead of copying the \(2x\)-strategy, you can simply subtract two tokens, leading to the position \(2x\) itself.
Similarly, it may be the case that the winning response to an opponent’s even move from \(2x\) is to take a single token, leading to odd \(\mathcal{P}\)-position \(2y+3\). Copying this strategy from the starting position \(2x+3\) would again lead to \(2y+6\). But in this case you can subtract four tokens leading to \(2y+3\) again.

It’s tempting to guess that, more strongly than pairing \(\mathcal{P}\)-positions and \(\mathcal{N}\)-positions in this way, subpract and similar subtraction games have a pairing of their nim-values, where the nim-value of an odd position always equals the nim-value of the even position three units smaller. But it’s not true. For instance, in subpract, a pile of four tokens has nim-value 1 while a pile of seven tokens has nim-value 4.

Other subtraction sets

Probably the most obvious choice of another subtraction set that begins \(\{1, 2, 4,\dots\}\) and has no larger odd numbers would be the powers of two, but they don’t give rise to an interesting subtraction game: the \(\mathcal{P}\)-positions are just the multiples of three. The same thing happens whenever there are no multiples of three in the subtraction set, as happens for instance with the telephone numbers and left factorials.

Another natural subtraction set to which this theory applies is the sequence of Hardy–Ramanujan integers (A025487), the numbers whose prime factorization \(2^a\,3^b\,5^c\,7^d\cdots\) has a non-increasing sequence of exponents \(a\ge b\ge c\ge d\ge \cdots\). They are:

\[1, 2, 4, 6, 8, 12, 16, 24, 30, 32, 36, 48, 60, 64, 72, 96, 120, \dots\]

These are a subset of the practical numbers so one would expect their subtraction game to have more-dense \(\mathcal{P}\)-positions. My implementation found that these \(\mathcal{P}\)-positions are:

\[0, 3, 10, 13, 20, 23, 38, 41, 66, 69, 76, 79, 94, 97, 104, 107, \dots\]

again obeying the offset-by-three pairing as it should, and otherwise having somewhat irregular intervals between its \(\mathcal{P}\)-positions.

The enumeration function of the series-parallel graphs and the cographs is even after its first term because of series-parallel duality; it begins

\[1, 2, 4, 10, 24, 66, 180, 522, 1532, 4624, 14136, 43930, \dots\]

These are not all practical; for instance, 10, 1532, and 43930 are not practical. The sequence of \(\mathcal{P}\)-positions for their subtraction game begins

\[0, 3, 6, 9, 12, 15, 18, 21, 26, 29, 32, 35, 38, 41, 44, 47, \dots\]

mostly differing by three between consecutive values but with occasional glitches where the larger multiple-of-three subtraction set values kick in.

And finally, if we subtract numbers that are one less than a prime, we get the subtraction set

\[1, 2, 4, 6, 10, 12, 16, 18, 22, 28, 30, 36, 40, 42, \dots\]

and the sequence of \(\mathcal{P}\)-positions

\[0, 3, 8, 11, 32, 35, 56, 59, 64, 67, 118, 121, 208, 211, 216, 219, \dots\]

Its small values have many five-unit gaps but that pattern appears to die out after the quadruple of \(\mathcal{P}\)-positions \(712, 715, 720, 723\).

(Discuss on Mastodon)