The number 7712, prime factorization `2^5 241`, appears in several integer sequences. An interesting one is A063776, the number of subsets of `\{1,2,...,n\}` which sum to 0 mod `n`. Investigating this sequence some more leads to a result about the number of losing positions in the game of Nim.
Recall that Nim is played with sticks in heaps: a move is to remove any number of sticks from a single heap and the loser is the player who cannot take any sticks. If there are `k` heaps of `n_i` sticks in heap `i`, then we write the position as `(n_1,n_2,...,n_k)`. If there are no sticks in any heap then the position is (0); if there is more than one heap then we will assume that all the `n_i` are positive (since a heap with 0 sticks doesn't affect the game).
Theorem. Fix `m \geq 1`. The number of losing positions `(n_1,n_2,...,n_k)` in the game of Nim where the `n_i` are distinct and less than `2^m` is `L_m = 2^{2^m - m - 1}`.
Example: if the heap sizes can be between 1 and 7 then `L_3 = 16`. The losing positions are: (4, 5, 6, 7), (3, 5, 6), (3, 4, 7), (2, 5, 7), (2, 4, 6), (2, 3, 6, 7), (2, 3, 4, 5), (1, 6, 7), (1, 4, 5), (1, 3, 5, 7), (1, 3, 4, 6), (1, 2, 5, 6), (1, 2, 4, 7), (1, 2, 3), (1, 2, 3, 4, 5, 6, 7), and (0).
The connection between this result about Nim and the number 7712 can be found in We will get to this result about Nim from the number 7712 through the paper An interesting result about subset sums by N. Kitchloo and L. Pachter. In that paper, the authors derive a formula for the number of subsets `B` of `\{1,2,...,n\}` such that `\sum_{b\in B} b \equiv k` mod `n`.
For example, there are 6 subsets of `\{1,2,3,4,5\}` whose members have sum congruent to 2 mod 5: `\{2\}, \{1,2,4\}, \{3,4\}, \{0,2\}, \{0,1,2,4\}, \{0,3,4\}`.
The formula given by Kitchloo and Pachter works for arbitrary `k` and `n` and involves Euler's totient function `\phi(t)` and the Mobius function `\mu(t)`. But for the special case that `k \equiv 0`, the formula reduces to
`N_n = 1/n \sum_{t|n, t odd} 2^{n/t} \phi(t)`
(By convention, the empty set is included in this count.) It's not hard to see that the number that started this, 7712, is `N_{17}`.
Kitchloo and Pachter also present a formula for the number of subsets of a finite abelian group `G` whose elements sum to the identity element (0) of `G`. This formula is not terribly complicated but all we will need is the special case that `G` is the direct sum of `m` copies of `\mathbb Z_2`. Then the formula for the number of subsets with zero sum is simply `2^{2^m - m}`.
Now, this count includes the empty set and the set containing just the zero element `(0,0,...,0)`. Of the others, half will contain only non-zero elements, so there are `2^{2^m - m - 1}` nonempty subsets with zero sum and either only non-zero elements or the single element `(0,...,0)`. This is the number given in the theorem; we need only connect it with losing positions in Nim.
There is an easy way to tell if a position in Nim is winning or losing: XOR the binary digits of the number of sticks in the heaps. If the result is all 0's then the position is losing, otherwise it is winning (and the person to move should take the number of sticks needed to change the XOR to all 0). Here's an example with 4 heaps:
| # sticks | Binary |
|---|---|
| 3 | 0011 |
| 9 | 1001 |
| 12 | 1100 |
| 15 | 1111 |
| XOR: | 1001 |
Since the XOR is 1001 and not 0000, this is a winning position for the player making the move; he should take 9 sticks from one of the heaps.
The connection between positions of Nim and `\mathbb Z_2^m` is obvious: map the number of sticks in a heap with its binary representation (padded to the left with 0's if needed), then a Nim position is a subset of `\mathbb Z_2^m`; the zero element of `\mathbb Z_2^m` corresponds to the zero game (0) of Nim. Since XOR binary digits and addition in `\mathbb Z_2^m` are equivalent, losing positions of unequal heap sizes are in one-to-one correspondence with subsets of `Z_2^m` with sum of `(0,...,0)`. This proves the theorem.
It turns out that the sequence `L_m` is sequence A016031, a de Bruijn sequence (the number of ways of arranging `2^n` bits in a circle so all `2^n` consecutive strings of length `n` are distinct). And that looks interesting as well...