In the 1901 paper that named the game Nim and provided its mathematical analysis, Charles Bouton defined “safe combinations”, positions that if you leave the game in this state, your opponent cannot win. In combinatorial game theory, these are \(\mathcal{P}\) positions (the previous player has already won), as opposed to \(\mathcal{N}\) positions (the next player can win).
Bouton gives a list of “the 35 safe combinations all of whose piles are less than 16”, working in three-heap Nim. Naturally it seemed sensible to check these, so I wrote a bit of Python code to do this. Bouton’s list is good. I realised I could easily adapt my code to find out how many \(\mathcal{P}\) positions there are for three-heap Nim games with other maximum heap sizes: 1, 2, 3, and so on.
And, having generated a sequence of integers, I naturally looked to see if it was in the OEIS. This is sometimes a good way to discover that your sequence of numbers is also found in some unexpected places. It wasn’t there! So I submitted it, and I just got the exciting email “N. J. A. Sloane published your changes”. So I present A363166: “Bouton numbers: a(n) is the number of P positions in games of Nim with three nonzero heaps each containing at most n sticks”.
This is my first OEIS submission, so it’s all very pleasing, even if I’m submitting a ‘new’ sequence inspired by a 1901 paper!
