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 93 nontrivial Octal-Games with at most 3 places and 0.6111... and Grundy's Game sorted by

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

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 n for which all G(n-1) are computed. This equals the size of the examined domain (counted included 0).

max G

maximal known value G(n)

index

index n of known maximum G(n)

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 all known G-values

average

average number of necessary previous values for computing all known G-values

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)

t

highest index of an octal-digit which contains a heap-break option for a specific game (in our cases an integer ≤ 3)

length

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

Support

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 a table of how fast n climbs for the next two power of all 3-place octal games.

A clickable image of max_{i ≤ n} G(i) of the strongest growing 3-place octal games for all n < 2²⁶.

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 = .0^k-17 games

	|	First position i for which G(i)=v
v	|	.017	.027	.037	.047	.057	.067	.077	.087	.097	.0107	.0117	.0127	.0137	.0147	.0157	.0k-17
1	|	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	k,  k>1
2	|	4	6	8	10	12	14	16	18	20	22	24	26	28	30	32	2k,  k>1
4	|	14	15	20	25	30	35	40	45	50	55	60	65	70	75	80	5k,  k>2
8	|	69	55	75	95	115	135	155	175	195	215	235	255	275	295	315	20k-5,  k>2
16	|	-	154	157	190	230	270	310	350	390	430	470	510	550	590	630	40k-10,  k>4
32	|	-	434	508	437	530	617	673	760	847	934	1021	1108	1195	1282	1369	87k-23,  k>7
64	|	-	1320	1521	1257	1125	1309	1461	1775	1800	1968	2178	2258	2435	2613	2791	178k-57,  k>13
128	|	-	3217	5894	3368	2691	4588	4905	4257	5558	5122	4921	4775	5499	5382	5903
256	|	-	9168	22337	11776	5425	19560	17925	16452	20650	20898	19807	12037	24460	11718	14724
512	|	-	35662	65758	31700	15857	91999	66730	107983	59402	64617	100373	43072	70414	29474	33142
1024	|	-	109362	157185	86894	74667	-	248642	-	177709	159710	445384	-	-	143411	104694
2048	|	-	-	450546	325183	-	-	745402	-	-	449929	1826020	-	-	-	498119
4096	|	-	-	1192769	1123380	-	-	1747901	-	-	1181581	-	-	-	-	2595342

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