# Sprague-Grundy Values of Octal-Games

## Introduction

These are special cases of Nim Games --- the so called Take-and-Break Games.
Given a heap of size n and two players who alternately have to make a move. On each turn a player must decrease the heapsize by a certain number and divide it possibly into several smaller heaps. The player who can't make a legal move, loses. Hence a heap of size 0 ist always lost and gets value G(0)=0. Generally a heap of size n has the value G(n) = min{ N0 \ Uj G(successor_positionj) } with j indicating all possible successor_positions.
The rule of these Take-and-Break Games is coded into a digit-string of the form d0.d1d2d3... where the i-th digit diindicates in how many non-empty heaps the chosen heap must be broken if its size was decreased by i.The digit di is interpretated as a binary-value, containing the two-power 2k if and only if the heap is allowed to be divided into k non-empty heaps. Of course d0 never contains 1 or 2. Octal-Games are a subset of these games, where both players has the same move options and are restricted at each move to dividing a heap into at most two parts, hence restricting any digit di to be atmost 1+2+4 < 8.
In the case of the range type (0) of the sparse space phenomenon, the set of these Sprague-Grundy-Values G(n) can be divided into a sparse set and its complement, called the common set. Values of the sparse set occur extremly rare, mostly only finite often. If these rare values die out then the infinte sequence of the G(n) must become periodic. A value G(n) belongs to the sparse set (in the range) if and only if population_count( G(n) AND m) AND 1 = 0 for a fixed game specific bitstring m.

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.0n7 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*83=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

Game sgv-sequence type bitstring rare last   max n max G index lost  ultimate depth period preperiod except

.0040000011112220333... 0 0001111111111... 184854 15869181 226 6279 50820532 32 827066 11905099
.0050001011222033411... 1 1110101001011... 148659 134182835227 1059 3022366 - - 3713078
.0060000111222033111... 0 0000000101111... 487832 67104903 226 6580 26683203 40 117632 16433620
.0070001112203311104... 0 0001110111111... 22476 5029983 228 1689 248902927 37 16170 5218954
.0140010010122123401... 0 0111111111111... 2037 64126 231 365 169860345 13 342 126438
.0150011010212230142... 0 0111111111111... 237 11973 235 101 2350397235 7 40 27036
.0160010122201014422... 0 0010111111111... 21442 180340840 229 1104 401309452 18 1474 78930408
.0240001122304112532... 0 ? 225 12371 30810166 26 28624
.0260001122304112533... 0 ? 225 37903 33220674 27 2235172
.0340011022314014312... 0 1111111111111... 1079 374473 234 256 26376 10 270 596840
.040000111220331110... 0 0001110111111... 22476 5029984 228 1689 248902928 38 16171 5218954
.0540010122234411163... 0 1011111111111... 38 796 - 41 33671802 3 3 16284 10015179 193235616 18
.0550011122231114443... 0 1111111111111... 6 43 - 8 51 2 1 20 148 259 2
.060001122031122334... 0 ? 225 33383 33550389 37 7537483
.0640001122334115533... 0 0111111111111... 6854 2104273309 231 523 275511554 3 2
.1040100010221224104... 1 1110111111111... 20 284 - 29 186892397 - - 4178 11770282 197769598 9
.1060100012221440106... 1 1011011111111... 15 1103 - 31 1937780317 - - 15343 328226140474 465384263797 25
.1140110011202120411... 0 1111111101111... 136867 67098692 226 1610 20501458 11 154
.1250102110213011302... 0 ? 225 65792 33500174 150 28575440
.1260100213321042503... 1 0111001110001... 20444 102973539 230 2222 265978 - - 58702391
.1270102210441220144... 1 1000001111111... 693 27106 - 56 24734 1190 20984 13551 4 46578 11
.1350112011203110312... 0 ? 225 47165 33446154 91 16773774
.1360110021302110223... 0 ? 225 41029 33153617 40 2769772
.140100102122104144... 0 0011111111111... 1896 178727 232 85 1839780623 172 2199 576735
.1420100222110332410... 1 1100011101111... 1357 117323 234 441 17142768844 - - 411815
.1430101222010422150... 0 1011111111111... 9417 2561883 228 148 26789789 13 81 10087243
.1460100222411133244... 0 1010111111111... 5817 307166 229 1521 200428954 3 3 324505
.1560110222441113224... 0 1101111111111... 15 357 - 23 1032 2 3 243 349 3479 8
.160100122140142140... 0 0111111111111... 53 13935 - 23 229790 7 837 21577 149459 105351 16
.1610102102132132430... 0 0111111111111... 489 23784 234 153 2744504036 14 429 107747
.1620100223110422610... 0 ? 225 65749 31107590 63 24565333
.1630102231042261042... 0 0001110111111... 2800497 33553435 225 39456 33326322 417 7050063
.1640100122344511632... 0 0000011001111... 333837 32952802 225 20543 3402756 3 3
.1650102132134436231... 0 1101111111111... (17#+87) - - 25 620 2 2 2597 1550 5181 4
.1660100223411662244... 0 1011111111111... 176 4281 234 173 3561617983 3 3 12850
.1670102234116224411... 0 1011111111111... 60 1303 237 64 332129728 2 2 7645
.1720110223011322440... 0 1011001111111... 2352 51381 231 387 2116001133 10 3947 116905
.1740110213221445642... 0 1101111111111... 57 674 239 82 312784191354 2 3 12547
.2040010120101231212... 1 0101110111111... 2245 83860 231 445 38455 - - 143454
.2050012010123123134... 1 1110010111111... 112 33944004 237 91 3114909246 - - 63095619
.2060010123201012323... 0 0011011111111... 10339 5668113 229 803 191546903 19 5184 9861529
.2070012120301245312... 1 0110100111111... 154 433920 236 126 60119768867 - - 776549
.2240012012312314304... 0 0000001111111... 1629867 32426611225 25465 20103641 26 198802
.2440010123234515673... 0 1000111111111... 65367 7596617 227 6718 115537003 3 3 11295819
.2450012123451567321... 0 0101111111111... 151 1352 235 142 10549340935 2 1 40663
.2640012345163251867... 0 1001111111111... 1992 46544 231 946 488110831 2 1 205974
.3140120120212312453... 0 0000011111111... 180147 39657176 226 3105 4636848 56 2770 20507380
.3240102130134023421... 1 1110010111111... 126 129608 237 109 7776114395 - - 386895
.3340120120312312435... 0 0000100101111... 3040144 33554031 225 32778 28929511 47 159618
.3360120312403120341... 0 0011111111111... 223 53899 234 90 4591503605 14 630 169971
.3420101232010323450... 0 ? 225 35576 33321026 68 636295
.3440101232451462321... 0 0011111111111... 8679 313574 228 1347 1158568 2 2 307675
.3460101232451672321... 0 ? 225 103309 31112181 2 2
.3540120124312352435... 0 1111110111111... 132 3227 - 113 1152 2 3 705 1180 10061916 44
.3560120212451675128... 0 1101111111111... 7 43 - 19 86 2 3 19 142 7315 2
.360102102132132430... 0 0111111111111... 516 11798 234 208 1762187846 14 429 17168
.3620102341023415237... 0 0011111111111... 529 43110 234 131 1614638854 11 227 239495
.3640102132134534231... 0 1111011111111... 977 13573224 233 564 6784 2 2 94736011
.3660102345162345768... 0 0111111111111... 827 643528 232 533 609293376 2 2 1115356
.370120123123403421... 0 0111011111111... 1583 20626 233 363 7775706553 13 407 1008822
.3710123103240234012... 0 0000001110111... 1498113 225 17474 27626301 42 40891 15399203
.3740120124312352435... 0 0111111111111... 246 2354 235 230 19481269639 2 3 6861
.3760120312435243514... 0 0111111111111... 510 1140540 - 176 341612 2 3 505866 4 2268248 42
.4040001122334115633... 0 1101101011111... 369 8024 234 263 5398126274 7 286 4621382
.4140011022344011322... 0 ? 225 192342 33380460 21 238588
.4160011223411663221... 0 1010111111111... 1014 10965 233 726 8167109156 3 16 11367
.4440001122334115633... 0 1101111111111... 364 72416309 234 212 4139813739 3 2 170177024
.450011223114432211... 0 1111111111111... 11 198 - 8 37 2 1 37 20 498 8
.4540011223411663221... 0 1011111111111... 17 124 - 41 14456117 2 1 4858 60620715 160949019 16
.560102241132446621... 0 1101101111111... 46 1795 - 64 22778 2 2 7405 144 326640 26
.5640102244113254768... 0 0110011111111... 1687 13275 231 1459 139723698 2 2 18757
.60012012312340342... 0 0111011111111... 1584 20627 233 363 7775706554 14 408 1008823
.6040012012312345345... 0 ? 225 192624 33505370 15 7943720
.6060012340123451234... 0 0111111111111... 53811 268412360228 1598 245416760 18 732 93636038
.640012341532154268... 0 0111110111111... 488 156751 233 262 1911635806 2 1 470403814
.644001234516325896a... 0 0111111111111... 31 511 - 64 333 2 1 604 442 3256 32
.740101232414623215... 0 1101101111111... 1386 15929 231 512 76103606 2 2 137102
.7440101232451672321... 0 0011011111111... 876 11268 232 733 382560700 2 2 43665
.760102341623416732... 0 0000000110011... 219248 5208068 226 16925 28902242 2 2 3822819
.7640102345162345768... 0 0111001111111... 12078 941007 228 5110 117968040 2 2 1423305
.7740123145671328954... 0 0101111111111... 352 3519 234 257 3285 1 0 25238
.7760123416321674581... 0 1001111011111... 503 7348 234 296 5487 1 0 18381

4.0040010123231454323... 0 0111111111111... 8914 43090760228 1996 20532406 3 3 23050686
4.0070012123454132825... 0 1111110101111... 2259 186900230 938 47129291 2 1 240392
4.0260012345613274165... 0 1000111111111... 392894 33532520 225 16817 4081741 2 1
4.0440010123234541673... 0 0011111111111... 184 1688235 293 17139683973 3 3 18849
4.0450012123454167828... 0 1111101111111... 34 497237 93 15355901532 2 1 4155
4.0640012345613285764... 0 1101011111111... 52 470 - 111 19114 2 1 420 16132 94272 45
4.3240120312435241352... 0 1110110111111... 271 5956 235 256 654707 2 3 19904
4.3270124312435213524... 0 1111111011111... 7111 1084182228 2247 7409767 1 0 1290657
4.344012021246164812a... 0 1110111111111... 14 271 - 35 190 2 3 164 51 998 4
4.3640120312435243521... 0 0111111111111... (6#+992) - - 33 2141 2 3 4221 62 11687 14
4.3670124312435213524... 0 0111111111111... 142 3508 236 101 64466228791 1 0 23739
4.4040012314324523513... 0 0111101111111... 132 1852 - 208 229872163 2 1 17840 145 6872982644 71
4.4060012345621874598... 0 1101111111111... 23 205 - 50 231573 2 1 212 44 294097 32
4.440012341632167458... 0 1001111011111... 504 7349 234 296 5488 2 1 18382

.6111...0012312341321461... 0 1011111111111... 171 2026 236 73 15336888688 2 1 21401399

Grundy's0001021021021321... 0 0111111111111... 1287 48399022 238 297 21544358589 42 1222 50808030
Couples0001201231234034... 0 0111011111111... 1585 20628 232 335 2135301626 15 409 1008824

Grundy's Game: the only option is to break any heap (of size greater than 2) into two heaps of different size.
Couples-are-forever: the only option is to break any heap of size greater than 2 into two heaps. It is the shifted variant of officiers (also denoted as .6) and the two-times shifted variant of .37. Moreover in this table of nontrivial octal-games four further games are equivalent: .776 with 4.44 and .04 with 0.007. Therefore, together with Grundy's Game and 0.6111..., it contains a total of 99= 93+4+2 entries.

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

The games 4.44, 0.04, 0.37 and Couples-are-forever are omitted in theses 6 listings (look up instead 0.776, 0.007, 0.6 and 0.6).

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
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

Game period* preperiod* miss density rare last+t max Gdepthautocorrelsolved
.45 20 498 67 0.134511200 837 1956
.156 349 3479 1919 0.551615360 2324366 0.8367 1967
.055 148 259 129 0.4980646 82028 0.8378 1976
.644 442 3256 2208 0.678131514 64604207 0.7285 1976
.356 142 7315 6419 0.8775746 191926 0.9155 1976
.165 1550 5181 251 0.0484- 252597620 0.9277 1976
.127 4 46578 15622 0.335469327109 5613551- 0.0000 1988-10-??
.56 144 326640 291858 0.8935461797 64740559 0.6042 1988-10-??
.16 149459 105351 3634 0.0345531393723215773 0.9148 1988-10-??
.376 4 2268248 1104157 0.48685101140543 176505866- 0.0000 1988-10-??
.454 60620715 160949019 147240872 0.914817127 41485898 0.3424 2000-12-31
.104 11770282 197769598 163669736 0.827620287 29417812 0.4993 2001-07-01
.106 328226140474 465384263797 151106 3115343152 0.3548 2002-05-21
.054 10015179 193235616170776546 0.883838799 4116284108 0.5809 2002-05-27
.354 1180 100619167912461 0.78641323230 113705193 0.7517 2002-05-28
*the length of the minimal (pre)period is given

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 2n-1(2k-1)+1with n,k positive integers, there are at most 2n 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.

### Correction

On 2020-Nov-12 Tomek Czajka from Los Angeles informed me that the game .161 has not the same standard form as .36 and their sgv-sequences differ firstly at index 520 and for infinitely many further. Thus I had overlooked this game which counts up to a total of 65 unsolved 2- and 3-place-octal games (and discovered a further flaw in WW p. 105).

## Misprints in Winning Ways chapter 4

(1st and 2nd edition, german & english):
• 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

Game bitstringrarelastmax nmax Gindexlostultimate

.0 17- - --986*-
.0 2700011101111111...22476 50299832281689 2489029273716170
.0 3700011111111111...184837 78971432235774 2925282 31827065
.0 47? > 2796000 223163908325820 291765270
.0 5701111010111111...8052 596514 2261306 55169705 2126851
.0 6700010011111111...34905 8242860223868 8110374 202900
.0 77?01111110111101...> 2422056 223112688254651 23930307
.0 8701111111111111...4196 13699174226628 55881099 21602
.0 9701111111111111...15942 786315 2251463 12051742 231943
.010701111101111111...> 615153 8386853223117777625502 254074
.011701111111011111...178988 77752022232187 2926368 24809
.012701111111111111...9144 258184 226945 34886850 269456
.013701111110111111...18418 33459253225979 26824407 275437
.014701111111011111...8954 60241502261216 27955191 285834
.015701111111001111...279460 83885612236020 8158733 296231
.0167? > 2690000 223102508044410 306628
.017701111111111111...54981 83804372232226 4384211 301223
.018701111111111111...155214 83882242232440 845568 311292
.019701111111111111...42430 46091072232876 1253051 33216131
.020700000000111011...> 946372 223111648203064 3413930
.021701111101101111...263675 83873202234104 7507947 341499
.022701111111111111...63803 21268332234096 4160051 3741646
.023701111111101011...> 721581 8388605223123597622353 3791185
.0247? > 2068425 223109518350696 371706
.025701111111111111... 148032 77728702234114 5087945 381775
Each game .0n7 has G(i)=0 for all i <= n.

 v .027 .037 .047 .057 .067 .077  .0n-17 | First position i for which G(i)=v | 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

Richard K. Guy and Cedric B. Smith, The G-values of various games, Proc. Cambr. Philo. Soc. V 52 (1959), pp. 514-526.
Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy, Winning Ways -- for Your mathematical Plays (1st edition), Vol. 1, Chap. 4, Academic Press 1982.
Anil Gangoli and Thane Plambeck, A Note on Periodicity in Some Octal Games, International Journal of Game Theory V 18 (1989), pp. 311-320.
Richard K. Guy, Unsolved Problems in Combinatorial Games, pp. 475-491, in Games of No Chance, ed. R. Nowakowski, MSRI Publications Vol. 29, 1996
Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy, Winning Ways -- for Your mathematical Plays (2nd edition), Vol. 1, Chap. 4, A.K. Peters, 2001.
Combinatorial Game Theory

URL created 2000-12-??
last updated 2021-05-05 14:29 UTC+2
Achim Flammenkamp