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 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²) 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 .
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.

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	1011000000000...	15	1103	-	31	1937780317	15343	328226140474	465384263797	25
.104	3	1110100000000...	20	284	-	29	186892397	4178	11770282	197769598	9
.205	3	0001101000000...	112	33944004	2³³	91	3114909246	61547715
.324	3	1110010000000...	126	129608	2³⁵	109	7776114395	386895
.207	3	0110100000000...	154	433920	2³²	122	1515503122	707475
.127	3	1000000000000...	693	27106	-	56	24734	13551	4	46578	11
.142	2	1100011100000...	1357	117323	2²⁹	428	232063111	206875
.204	3	1010001000000...	2245	83860	2²⁹	445	38455	108594
.126	3	1000110001110...	20441	47561551	2²⁶	2222	265978	30945308
.005	3	1110101001000...	67585	33367128	2²⁵	1059	3022366

Achim Flammenkamp
updated 2006-09-12