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 the book Winning Ways (for your mathematical plays), Elwyn R. Berlekamp, John H. Conway and Richard K. Guy describe the Sparse Space Phenomenon which enables computing algorithms for the sequence of the G(n)-values of octal games of runtime of order O(n) compared to order O(n2) of the naive approach. This sparse space phenomenon was identified first by E. R. Berlekamp (1980?). It is based on the fact, that for a given fixed binary value, the so-called mask, G-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 G-value of an even number of 1-bits, the so-called rare values, with a G-value of an odd-number of 1-bits (both regarded in their masked binary representation).
Unfortunately for some octal games there exists no such Sparse Space. Here the structure of the G-values exhibit a similar phenomenon together with their positions(-domain) -- which was firstly discovered by A. Flammenkamp in 2001. For historical reference, my very first public accessable "octal game web-page" from december 2000. But beware, it contains errors -- even in the definition of sparse space. :-/

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. This definition is almost identical to the classical Sparse Space definition where the right side of the equation equals 0 and therefore doesn't depend explicitly on n. The function population_count(n) gives the number of 1-bits in the binary representation of a integer n.
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 (also called nim-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 with its domain.

Table (with sortable columns): Nontrivial Octal Games with at most three digits and a Sparse Position-Space


Game t bitstring bitmask rare last max n max G index lost depth average period preperiod except
.106 3 1011011111111... 10010215 1103 - 31 1937780317 0.1599176 15343 16.44 328226140474 465384263797 25
.104 3 1110111111111... 1000220 284 - 29 186892397 0.1233355 4178 17.27 11770282 197769598 9
.205 3 1110010111111... 10110002112 33944004 243 94 1140389987762 0.0376039 81239243 113.73
.324 3 1110010111111... 10110002126 129608 242 113 642064155864 0.0369717 487269 135.79
.207 3 0110100111111... 11010012154 433920 240 128 341715359271 0.043403 882720 142.63
.127 3 1000001111111... 1111102693 27106 - 56 24734 0 13551 3.50 4 46578 11
.142 2 1100011101111... 10001110021357 117323 240 447 304983208467 0.0015461 471721 1711.41
.204 3 0101110111111... 100010122245 83860 238 465 234528691963 0.0009675 256102 3139.34
.126 3 0111001110001... 111000110001220444 102973539 234 2222 265978 0.0000014 85616111 33533.73
.005 3 1110100011011... 100111010002126651 8474963595 233 1089 1661343568 0.0065595 4237481797 21245.55
The column lost denotes the fraction of lost positions to all positions.


Achim Flammenkamp
updated 2026-11-12 17:55 UTC+1