Sparse- and Common-Positions of Sprague-Grundy Values of Octal-Games

To memorize, the rule of any Octal-Games is coded into a digit-string of the form d0.d1d2d3... and all digits di must be non-negative integers less than 8 (therefore the name Octal-Game). The digit di indicates binary-coded in how many non-empty heaps the chosen heap must be broken if its size is decreased by i.
In Winning Ways, Berlekamp, Conway and Guy describe the Sparse Space Phenomenon which enables computing algorithms for the sequence of the G(n)-values of running time of order O(n) compared to order O(n2) of the naive approach. This sparse space phenomenon was identified first by Berlekamp (1980?). It is based on the fact, that for a given fixed binary value, the so-called mask, values consisting of an odd number of 1-bits in their masked binary representation, the so-called common values, can only be produced by the XOR-operation of a value of an even number of 1-bits, the so-called rare values, and a value of an odd-number of 1-bits (both regarded in their masked binary representation).
Unfortunately for some Octal-games there is no such Sparse Space. Here the structure of the values exhibit a similar phenomenon in the positions. Strictly speaking typically there is a Sparse Space Phenomenon in the range but some times you need also the domain.

Let us consider only those Octal-Games which has exactly one digit di which is greater than 3, e.g. exactly one option exists to break a heap into exactly two non-empty heaps. Define t to be the index i of this digit di.
For historical reasons -- specifically WW chapter 4, section extra, paragraph 'Sparse Space Spells Speed' -- the notation of an (infinite) bitstring is introduced which is the 1-complement of a (finite) binary number called the bitmask. For a fixed game and a specific bitstring m, a position n belongs to the sparse set if and only if   population_count( G(n) AND m) AND 1 = n-t AND 1 .
As a simple example, look at the octal game .051. This game has period length = preperiod length = 48 and a maximal value of 5. Choose a bitstring m to be 111111... and then its sgv-sequence is: 

 0 1 2 3 4 5 6 7 8 91011121314151617181920212223242526272829303132333435363738394041424344454647   n

 0 0 1 1 1 0 2 2 1 3 4 0 1 1 1 3 2 2 2 3 4 0 1 5 4 3 2 2 2 3 1 0 1 0 4 3 2 2 2 0 1 0 1 0 4 3 2 5   preperiod
 4 0 1 0 1 0 2 3 2 3 4 0 1 0 1 3 2 3 2 3 4 0 1 0 4 3 2 3 2 3 1 0 1 0 4 3 2 3 2 0 1 0 1 0 4 3 2 3   period

 * 0 1 * 1 0 1 * 1 0 1 0 1 * 1 0 1 * 1 0 1 0 1 0 1 0 1 * 1 0 1 0 1 0 1 0 1 * 1 0 1 0 1 0 1 0 1 0   population count G(n)  AND 1
For this chosen bitstring only in the preperiod a rare value occurs at position 0, 3, 7, 13, 17, 27, and 37. Thus the sparse space contains only these 7 indices.

Values of the sparse set occur extremly rare, mostly only finite often. If these sparse values die out and the common values remain bounded the infinte sequence of the G(n) must become periodic.
A quick practical indicator which kind of sparse space a specific game has, is the number of lost-positions of its G(n)-sequence --- if this seems to grow rapidly, surely no sparse space in the range exists. Moreover an octal game which has break-options at di for i with different parities can not exhibit such a sparse space in its domain.

Nontrivial Octal-Games with at most three digits and a Sparse Position-Space

Game t bitstring sparse last max n max G index depth period preperiod except
.106 3 1011011111111... 15 1103 - 31 1937780317 15343 32822614047446538426379725
.104 3 1110111111111... 20 284 - 29 186892397 4178 11770282 197769598 9
.205 3 1110010111111... 112 33944004 237 91 3114909246 63095619
.324 3 1110010111111... 126 129608 237 109 7776114395 386895
.207 3 0110100111111... 154 433920 236 126 60119768867 776549
.127 3 1000001111111... 693 27106 - 56 24734 13551 4 46578 11
.142 2 1100011101111... 1357 117323 234 441 17142768844 411815
.204 3 0101110111111... 2245 83860 231 445 38455 108594
.126 3 0111001110001... 20444 102973539 230 2222 265978 58702391
.005 3 1110101001011... 148659 134182835 227 1059 3022366

Achim Flammenkamp
updated 2021-04-05