Grundy's game split a heap, but never in half
A move takes one heap and splits it into two heaps of different sizes. Heaps of 1 and 2 cannot be split; whoever makes the last split wins. Every heap size n has a Grundy value G(n), and a position is lost for the player to move exactly when its heaps' values XOR to 0. Pick a heap: cuts marked ✓ leave XOR 0 behind, ✗ do not.
value of the position
checked against the literature
G(n), and the rare sparse values
the sparse heaps
Why the heaps add up
A heap of n is worth G(n) = mex { G(a) ⊕ G(n − a) : a < n − a }, the smallest number not among the values of its splits; by the Sprague–Grundy theorem a position of several heaps, where each turn splits one of them, is worth the XOR of their values. G(n) = 0 only 42 times, the last at n = 1222; nobody knows whether the sequence is eventually periodic.
Sparse space
Call a value common when its bits other than the lowest have odd parity, sparse otherwise (Flammenkamp's mask 0111…10). Common ⊕ common and sparse ⊕ sparse are sparse; common ⊕ sparse is common. Almost every heap has a common value, so every common option of a heap comes from a split with exactly one of the few sparse heaps — about 1,300 lookups instead of n/2. The sparse values below the answer still have to be ruled out, by scanning splits a = 1, 2, … until each has appeared; on average about 3,100 splits. When the scan runs out, a new sparse heap has been found. The last known one is n = 48,399,022.