Sprague-Grundy Values of Octal-Games

Introduction

On this web-page (and its sub-pages) results for all octal games of notation 0.???, 4.??? -- here a ? indicates any octal digit 0-7 -- , 0.61111...., Grundys-Game and 0.0ⁿ7 with n <= 25 -- this last notation indicates you must always reduce a heap by n tokens and 0, 1 or 2 heap(s) may remain -- are given.

A compendium containing all 2*8³=1024 at most 3 place octal games to find or match its standard form.

Next a listing of all the 167 standard forms to look up basic attributes and the same listing sorted by their sgv-sequences.
In each line of this listing presents from left to right a game-name, its the period- and preperiod lengtn, its the maximum sg-value, its number of lost postions and the first 40 values of its sgv-sequence. If the sum of period and preperiod length of a game is larger than 250 it is left blank. In those 93 cases the game is called non-trivial and it is listed in the following table.

Nontrivial Octal-Games with at most 3 places

Listing of these nontrivial Octal-Games with at most 3 places sorted by

• size of sparse space
• largest index of a rare value
• maximal size of nim-value
• index of maximal nim-value
• depth (maximal number of necessary previous values)
• largest index of a lost value

legend:

Game

name of the game

sgv-sequence

the sequence of the G-values starting from n=0

type

kind of sparse space phenomenon: 0 = in range / 1 = in domain (sparse-position-space)

bitstring

infinite 0-1-sequence describing the sparse space with lowest significant bit first

bitmask

finite binary number describing the sparse space with lowest significant bit last, mirrored 1-complement of bitstring

rare

number of known rare values resp. size of sparse set

last

largest known index of a rare value

max n

maximum searched n

max G

maximal found value G(n)

index

index of known maximum

lost

number of known lost sg-values i.e. number of indices n with G(n)=0

ultimate

largest known index with a lost sg-value

depth

maximal number of necessary previous values for computing current G-value

period

minimal period length

preperiod

minimal preperiod length

except

last exceptional sg-value in the preperiod

miss

number of values in the preperiod which are not covered by the period if this would be shifted by multiples of its length

auto

shift < period length of maximal autocorrelation of the sgv-sequence

correl

maximal autocorrelation coefficient (shift is given by auto)

length

length/depth (<= last+t) of the mex-shift register to simulate the game after the last rare value has occured

Nontrivial Octal-Games with known Structur

To prove a period length p of such a game computationally, it is sufficient to verify the equation G(i+p) = G(i) only for t+ max { last, depth } many successive sg-values with t the largest index of a non-zero digit of the game's name (in the case of a sparse position space p should be even).
There are still 65 and 8 unsettled 2-place- respectively 3-place-octal games (and Grundy's Game and 0.6111...).

Remark: if there are only finitely many rare values, the game will become ultimatively periodic. For a given octal game, let a denote the number of digits which allows a take remaining still something, i.e. the number of digits containing 2, and let b denote the number of digits which allows a break in two heaps, i.e. the number of digits containing 4. Each rare value can prohibit a common value. Thus if all the, say s, rare values cover different (and the smallest) common values for all the move options, then at last the a+s*b+1 common value must be the sg-value. For a given bitstring m having the unique 1-complement representation 2^n-1(2k-1)+1with n,k positive integers, there are at most 2ⁿ successive rare respectivley common values (n-1 is the number of successive lowest 0-bits in m). So we get a quantitive upper bound for the maximal occuring sg-value. Thus, the mex-rule can be considered as a shift-register of length largest rare index + t and its sum of period length and preperiod length must be bounded by (a+s*b+1)^last+t.

Finally a tabular overview of the increase of the maximum as n climbs from the strongest growing 3-place octal games and of how fast n climbs for the next two power of all 3-place octal games.

The concept of sparse position space.

Correction

Misprints in Winning Ways chapter 4

• p. 96   Officers (.6): G(10344)=256
  
• p. 101   Game locator for 2-place game .27: .26
  
• p. 103   Game locator for 3-place game .314:
  
• p. 105   missing entry for 3-place game .161:
  
• p. 112   Sparse Space Spells Speed (column .000007): G(15857)= 512
  
• p. 112   Sparse Space Spells Speed (column .000007): ...1101011110
  
• p. 112   Sparse Space Spells Speed (new column .007): ...1110111000
  

Further informations on the .00...007 games

	|	First position i for which G(i)=v
v	|	.027	.037	.047	.057	.067	.077	.0n-17
1	|	3	4	5	6	7	8	n
2	|	6	8	10	12	14	16	2n
4	|	15	20	25	30	35	40	5n
8	|	55	75	95	115	135	155	20n-5
16	|	154	157	190	230	270	310
32	|	434	508	437	530	617	673
64	|	1320	1521	1257	1125	1309	1461
128	|	3217	5894	3368	2691	4588	4905
256	|	9168	22337	11776	5425	19560	17925
512	|	35662	65758	31700	15857	91999	66730
1024	|	109362	157185	86894	74667	-	248642
2048	|	-	450546	325183	-	-	745402
4096	|	-	1192769	1123380	-	-	1747901

The preceeding table is an extension of the table in 'Winning Ways for Your Mathemtical Plays', chapter 4, section Extras, paragraph 'Sparse Space Spells Speed'.

References