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₀.d₁d₂d₃... 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 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(n²) 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 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 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 d_i for i with different parities can not exhibit such a sparse space with 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³⁷	91	3114909246	63095619
.324	3	1110010111111...	126	129608	2³⁷	109	7776114395	386895
.207	3	0110100111111...	154	433920	2³⁶	126	60119768867	776549
.127	3	1000001111111...	693	27106	-	56	24734	13551	4	46578	11
.142	2	1100011101111...	1357	117323	2³⁴	441	17142768844	411815
.204	3	0101110111111...	2245	83860	2³⁴	445	38455	164420
.126	3	0111001110001...	20444	102973539	2³¹	2222	265978	76798817
.005	3	1110100011011...	126626	2009138943	2³¹	1089	1661343568	1004569471

Achim Flammenkamp
updated 2026-08-19