# 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 *d*_{0}.d_{1}d_{2}d_{3}...
and all digits *d*_{i} must be non-negative integers less than 8 (therefore the name Octal-Game).
The digit *d*_{i} 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(n*^{2}) 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 *d*_{i} 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 *d*_{i}.

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 *d*_{i} 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 | 328226140474 | 465384263797 | 25 |

.104 | 3 | 1110111111111... | 20 | 284 | - | 29 | 186892397 | 4178 | 11770282 | 197769598 | 9 |

.205 | 3 | 1110010111111... | 112 | 33944004 | 2^{37} | 91 | 3114909246 | 63095619 |

.324 | 3 | 1110010111111... | 126 | 129608 | 2^{37} | 109 | 7776114395 | 386895 |

.207 | 3 | 0110100111111... | 154 | 433920 | 2^{36} | 126 | 60119768867 | 776549 |

.127 | 3 | 1000001111111... | 693 | 27106 | - | 56 | 24734 | 13551 | 4 | 46578 | 11 |

.142 | 2 | 1100011101111... | 1357 | 117323 | 2^{34} | 441 | 17142768844 | 411815 |

.204 | 3 | 0101110111111... | 2245 | 83860 | 2^{31} | 445 | 38455 | 108594 |

.126 | 3 | 0111001110001... | 20444 | 102973539 | 2^{28} | 2222 | 265978 | 40637003 |

.005 | 3 | 1110101001011... | 95660 | 67070800 | 2^{26} | 1059 | 3022366 |

Achim Flammenkamp

updated 2012-11-10