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 ∈ N0 and two players who alternately have to make a move. On each turn a player must decrease the size of the/any heap by a certain positive integer and then possibly divide this heap into several smaller heaps. The player who can't make a move (if it is his turn) 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) } where j runs over 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 di indicates in how many non-empty heaps the chosen heap must be broken if its size was decreased by i. The digit di is interpreted 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.xyz, 4.xyz -- with x, y, z ∈ {0,1,2,...,7} indicates any octal digit 0-7 -- , 0.61111...., Grundys-Game and 0.0k-17 with 1 <= k <= 32 (this last notation indicates you must always reduce the size of any heap by k 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 of all 172 standard forms.

Or enter a game code (at most 3 octal digits after the mandatory dot are permitted) and press .

Table 1: The 172 nonequivalent Octal Games with at most 3 places

Game sgv-sequence (G(n))n=0 max G lost pv

0.00 0000000000000000000000000000000000000000... 0 # 1 0
0.01 0010000000000000000000000000000000000000... 1 #+3 1 3
0.02 0001100110011001100110011001100110011001... 1 2#+1 4 1
0.04 0000111220331110433322244055222330501113...≥ 722≥ 38
0.05 0010101010101010101010101010101010101010... 1 #+1 2 1
0.06 0001122031122334405334221130221144552647...≥ 775≥ 32
0.07 0011203110332240522330113021104527401120... 9 5#+11 34 53
0.11 0110000000000000000000000000000000000000... 1 #+1 1 3
0.12 0100110011001100110011001100110011001100... 1 2#+1 4 1
0.14 0100102122104144122120104126164140102126...≥ 52≥ 172
0.15 0110112212211011221221101122122110112212... 2 #+1 10 1
0.16 0100122140142140142142102142145142142142...≥ 22≥ 7
0.17 0110213011322341532231103120114426411021... 7 4#+5 34 33
0.22 0012012012012012012012012012012012012012... 2 #+1 3 1
0.26 0012301230123012301230123012301230123012... 3 #+1 4 1
0.31 0120101010101010101010101010101010101010... 2 #+1 2 3
0.32 0102102102102102102102102102102102102102... 2 #+1 3 1
0.34 0101201031212030312120303121203031212030... 3 2#+3 8 7
0.35 0120102120102120102120102120102120102120... 2 2#+1 6 1
0.36 0102102132132430432412312012415415415210...≥ 187≥ 14
0.37 0120123123403421321021451451201231234234...≥ 284≥ 13
0.44 0001122331144332211442266441122771144332... 8 3 24143
0.45 0011223114432211422644112271144322114827... 8 220498
0.51 0111111111111111111111111111111111111111... 1 1 1 1
0.52 0102210321032103210321032103210321032103... 3 #+2 4 4
0.53 0112210224012211224112211224112211224112... 4 3 9 11
0.54 0101222411122241112224111222411122241112... 4 2 7 3
0.56 01022411324466211768411654811c456113c668...≥ 64≥ 2
0.57 0112211221122112211221122112211221122112... 2 1 4 1
0.64 001234153215426812374582954768146274b238...≥ 256≥ 2
0.71 0121010101010101010101010101010101010101... 2 #+1 2 3
0.72 0102310231023102310231023102310231023102... 3 #+1 4 1
0.74 0101232414623215176851ab26845a6215156268...≥ 414≥ 2
0.75 0121212121212121212121212121212121212121... 2 1 2 1
0.76 01023416234167321675289652871a4371a42861...≥ 1637≥ 2
0.77 0123143214264127143214674128547218674123... 8 1 12 71
4.12 0112204211221421122142112214211221421122... 4 2 7 6
4.30 0120202020202020202020202020202020202020... 2 #+1 2 2
4.32 0120312031203120312031203120312031203120... 3 #+1 4 1
4.44 00123416321674581a54761236143218a4eg1234...≥ 296≥ 2
4.72 0124124124124124124124124124124124124124... 4 1 3 1
0.002 0000111000111000111000111000111000111000... 1 3#+1 6 1
0.004 0000011112220333111104433332222444055522...≥ 490≥ 29
0.005 0001011222033411015433322216010452216657...≥ 512≥ 457
0.006 0000111222033111224333552144333222111405...≥ 1220≥ 39
0.014 0010010122123401051212530345121123033234...≥ 311≥ 13
0.015 0011010212230142145122323401451251234234...≥ 84≥ 7
0.016 0010122201014422161604212766151284612108...≥ 389≥ 18
0.017 0011120231140451320211140261640411120261... 8 10#+4 60 15
0.022 0001120011200112001120011200112001120011... 2 2#+1 5 1
0.024 0001122304112532411556031251481421967422...≥ 532≥ 26
0.026 0001122304112533411253044211334421156322...≥ 654≥ 14
0.034 0011022314014312210514563248140276245841...≥ 256≥ 10
0.044 0000111222333111444333222111444222666444... 8 4 36214
0.045 0001112223311144433222111442226644411122... 8 3 32189
0.051 0011102213401113222340154322231010432220... 5 12#+10 48 48
0.054 0010122234411163222411666734451116735441...≥ 34≥ 3
0.055 0011122231114443222111422264441112227111... 8 2 148259
0.064 0001122334115533221154422668411223374455...≥ 512≥ 3
0.101 0101000000000000000000000000000000000000... 1 #+2 1 4
0.104 0100010221224104015661228104015662548101...≥ 21≥ 7593
0.106 0100012221440106212421045166512451065304...≥ 27≥ 10461
0.111 0111000000000000000000000000000000000000... 1 #+1 1 4
0.114 0110011202120411041152415241120112043224...≥ 700≥ 11
0.115 0111011122212221110111222122211101112221... 2 #+1 14 1
0.116 0110021202110441524112041204115442520215... 12 13#+21 96139
0.121 0102100110011001100110011001100110011001... 2 2#+2 4 4
0.122 0100211002110021100211002110021100211002... 2 2#+1 5 1
0.123 0102210021100211002110021100211002110021... 2 2#+2 5 5
0.124 0100110213021301130233223425042532233203... 9 9#+23 62122
0.125 0102110213011302342234253225320311031201...≥ 698≥ 123
0.126 0100213321042503150415041304130223445372...≥ 1536≥ 75
0.127 0102210441220144617701226144812781072681... 56 1190 446578
0.132 0110021100211002110021100211002110021100... 2 2#+1 5 1
0.134 0110011203120311031223322435143522332213... 7 8#+10 62 60
0.135 0112011203110312243224352235221301130211...≥ 838≥ 78
0.136 0110021302110223342514223342011203120514...≥ 778≥ 34
0.141 0101101221241011212212412112122124121121... 4 4 11 14
0.142 0100222110332410632310162240115338406235...≥ 386≥ 173
0.143 0101222010422150472280412228104221504722...≥ 16≥ 13
0.144 0100122224411112222441111222244111122224... 4 3 10 4
0.145 0101122224111122224111122224111122224111... 4 2 9 3
0.146 0100222411133244466623111766842117653481...≥ 1092≥ 3
0.147 0101222441112224411122244111222441112224... 4 2 8 3
0.152 0110222010432310132240104223101323401022... 4 12#+1 48 2
0.153 0111222110222440112221112224411122211122... 4 3 14 16
0.154 0110112222241111122222411111222224111112... 4 2 11 4
0.156 0110222441113224446662111576688111265558... 23 2 3493479
0.157 0111222111222111222111222111222111222111... 2 1 6 1
0.161 0102102132132430432412312012415415415210...≥ 138≥ 14
0.162 0100223110422610342660542330142836514230...≥ 534≥ 28
0.163 0102231042261042261043221043265043261053...≥ 131≥ 191
0.164 01001223445116322341566738211a76675541a8...≥ 1546≥ 3
0.165 0102132134436231281265445182182136c56481... 25 2 15505181
0.166 0100223411662244113385446633118826441933...≥ 150≥ 3
0.167 010223411622441133544663315866a44336aa44...≥ 52≥ 2
0.171 0112211021401122112214211221122142112211... 4 3 11 12
0.172 0110223011322440632240163220116334411035...≥ 306≥ 10
0.173 0112231043201122351432211023741322104627... 7 5#+3 40 21
0.174 0110213221445642231154128865741b22688a1b...≥ 73≥ 2
0.176 0110223441162234411663324116633441166334... 6 2 8 24
0.204 0010120101231212314303143232432324520215...≥ 445≥ 545
0.205 0012010123123134034532325321020254734204...≥ 55≥ 2538
0.206 0010123201012323451232345401034242175453...≥ 686≥ 19
0.207 0012120301245312124303021435821363041212...≥ 79≥ 2839
0.224 0012012312314304314213210214264164261201...≥ 594≥ 25
0.226 0012340123451234512305123451234512345123... 5 4 5 21
0.244 00101232345156732321589767654548232ab454...≥ 1604≥ 3
0.245 001212345156732128976564c9212a7452c73d21...≥ 129≥ 2
0.264 0012345163251867524816a45267a5187e615386...≥ 739≥ 2
0.312 0120201010101010101010101010101010101010... 2 #+2 2 5
0.314 0120120212312453035121321212562154020621...≥ 365≥ 56
0.316 0120212301030123212301030123212301030123... 3 3#+2 12 4
0.324 0102130134023421320341346201253167813416...≥ 71≥ 2417
0.331 0123012012012012012012012012012012012012... 3 #+1 3 4
0.334 0120120312312435034261241302172478420615...≥ 945≥ 46
0.336 0120312403120341236123051306413524630143...≥ 65≥ 14
0.342 0101232010323450232540102321456720547623...≥ 740≥ 66
0.344 0101232451462321458767a141232641482321a1...≥ 715≥ 2
0.346 010123245167232158676a548923ab45832ba158...≥ 2048≥ 2
0.351 0121201021212010212120102121201021212010... 2 2#+1 8 1
0.353 0121202020202020202020202020202020202020... 2 #+1 2 4
0.354 0120124312352435135247247864762786836c74...≥ 113≥ 2
0.356 0120212451675128262815b79581212c25856181... 19 2 1427315
0.362 0102341023415237142370123750132548625487...≥ 87≥ 11
0.364 0102132134534231251257457482962968764721...≥ 564≥ 2
0.366 01023451623457689127685432915b3284ab3659...≥ 517≥ 2
0.371 0123103240234012416320123413421073416218...≥ 514≥ 42
0.373 0123401234152314721043214026402340123415... 7 4#+1 28 2
0.374 0120124312352435135247247864762786936974...≥ 201≥ 2
0.375 0123124321342748148124814381482148148124... 8 1 18 37
0.376 012031243524351432645867a827362746539253...≥ 162≥ 2
0.404 0001122334115633221108772554011228845566...≥ 256≥ 7
0.414 00110223440113223445663223118763aa011876...≥ 2257≥ 18
0.416 00112234116632210668445a1783324166884aac...≥ 674≥ 3
0.444 0001122334115633221188776554411228845566...≥ 196≥ 3
0.454 00112234116632211668445a1183344766884116...≥ 34≥ 2
0.512 0111222101222101222101222101222101222101... 2 #+1 6 3
0.524 0102210441670122614461870187614761078167... 8 7#+1 52 1
0.532 0112240122411224112241122411224112241122... 4 2 5 7
0.536 0112241122411224112241122411224112241122... 4 1 5 1
0.564 010224411325476823a768932c6543211945aace...≥ 1276≥ 2
0.604 0012012312345345321321025475476892012396...≥ 1486≥ 12
0.606 0012340123451234562345673416789167891437...≥ 987≥ 18
0.644 001234516325896a5496ea42367g49eagh94ef19... 64 2 4423256
0.744 01012324516723218967a45981aba45961ab3989...≥ 636≥ 2
0.764 010234516234576891a76854326154328eab59ge...≥ 4285≥ 2
0.772 0123416241634163416341634163416341634163... 6 1 4 8
0.774 01231456713289546c219645cd238956dc3296ag...≥ 257≥ 1
4.004 0010123231454323215152767548926269894572...≥ 1443≥ 3
4.005 0012123145132121527526126268458361515615... 8 2 79 31
4.007 0012123454132825476728237674521218454a81...≥ 850≥ 2
4.024 0012314314214264164134132142842812314314... 11 2 60 2
4.026 00123456132741652389625814723168432189ab...≥ 2251≥ 2
4.044 001012323454167328945a6739d515a7698ghaef...≥ 269≥ 3
4.045 00121234541678281ab7614ef321214f8d6dcbg2...≥ 76≥ 2
4.064 001234561328576423187452891b4dc18ab625cg...≥ 111≥ 2
4.102 0111222044211122214421112221442111222144... 4 2 10 8
4.122 0112204311224431122443112244311224431122... 4 2 7 6
4.304 0120212461528156261625186818261526158281... 11 2 21 25
4.323 0124302130213021302130213021302130213021... 4 #+1 4 4
4.324 012031243524135247564726879165742594273c...≥ 228≥ 2
4.327 0124312435213524786478697462531253421342...≥ 1930≥ 1
4.344 012021246164812a219d419ag12ag1464b2a2d1a... 35 2 51998
4.364 0120312435243521352475647869286974657425... 33 2 6211687
4.367 0124312435213524786478697469742531253421...≥ 88≥ 1
4.404 0012314324523513245678976986745785423453...≥ 167≥ 2
4.406 00123456218745981456781f65482gb65h123b8g...≥ 49≥ 2
4.444 00123456732897654328945cd982345fe3289765... 17 2 24143
4.722 0124612561256125612561256125612561256125... 6 1 4 4
4.726 0124612741824187b124812741824187b1248127... 11 1 16 5
4.766 01246128a1d2g14de184d12481dg8142d148d1g4... 16 1 20 19
p denotes the minimal length of the period and v denotes the minimal length of the preperiod.
If in the column max G a lower bound is given, then this comes from the largest value of the first 216 sg-values.
# counts the number of considered periods. So, the number (default is 1) in front of the # is the number of lost positions in a period.
If v+p > 216 for a game then the corresponding entries of v and p are left blank.
For historical reasons, in the case v+p > 250 there are 93 octal games which are called non-trivial. Moreover here is a listing of the "most interesting trivial" games (10 < v+p < 210) sorted by the sum of preperiod length and period length indicating their sparse-space structure if it exists.

Table 2 (with sortable columns): Nontrivial Octal Games with at most 3 places

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

.004 0000011112220333... 0 0001111111111... 1112184854 15869181 231 6589 1641920418 32 827066 26668894 415344.59
.005 0001011222033411... 1 1110100011011... 100111010002126651 8474963595 233 1089 1661343568 - - 4237481797 21245.55
.006 0000111222033111... 0 0000000101111... 1011111112512008 832962245 230 6699 945775613 40 117632 428107592 679447.49
.007 0001112203311104... 0 0001110111111... 1000111222476 5029983 234 1691 16147792901 37 16170 7845114 34011.46
.014 0010010122123401... 0 0111111111111... 122037 64126 239 426 262345068862 13 342 263405 3558.18
.015 0011010212230142... 0 0111111111111... 12237 11973 242 112 27283228139517 40 34014 388.09
.016 0010122201014422... 0 0010111111111... 1011221442 180340840 234 1143 5293609178 18 1474 161469089 47120.73
.024 0001122304112532... 0 ? ? > 102458500 228 67310 257443638 26 28624
.026 0001122304112533... 0 ? ? > 103557172 228 176970 261364011 27 2235172
.034 0011022314014312... 0 1111111111111... 021079 374473 240 259 302490578942 10 270 1782211024 1444.81
.04 0000111220331110... 0 0001110111111... 1000111222477 5029984 234 1691 16147792902 38 16171 7845115 34012.46
.054 0010122234411163... 0 1011111111111... 10238 796 - 41 33671802 3 3 16284 103.59 10015179 193235616 18
.055 0011122231114443... 0 1111111111111... 026 43 - 8 51 2 1 20 12.97 148 259 2
.06 0001122031122334... 0 ? ? > 114600346 228 182613 264842000 39 134136243
.064 0001122334115533... 0 0111111111111... 127415 34258169715235 546 21471815066 3 2 171290848578755.05
.104 0100010221224104... 1 1110111111111... 1000220 284 - 29 186892397 - - 4178 17.67 11770282 197769598 9
.106 0100012221440106... 1 1011011111111... 10010215 1103 - 31 1937780317 - - 15343 16.44 328226140474 465384263797 25
.114 0110011202120411... 0 1111111101111... 1000000002549882 536839512 229 1670 395200415 11 154 268020165 176905.43
.125 0102110213011302... 0 ? ? > 43860017 227 131785 133024914 158 57108572
.126 0100213321042503... 1 0111001110001... 111000110001220444 102973539 234 2222 265978 - - 85616111 33533.73
.127 0102210441220144... 1 1000001111111... 1111102693 27106 - 56 24734 1190 20984 13551 3.50 4 46578 11
.135 0112011203110312... 0 ? ? > 54832158 227 123289 131052441 96 53716054
.136 0110021302110223... 0 ? ? > 56036822 227 115459 134202636 46 121496736
.14 0100102122104144... 0 0011111111111... 1121896 178727 239 102 405178406154 172 2199 2286677 2153.19
.142 0100222110332410... 1 1100011101111... 10001110021357 117323 240 447 304983208467 - - 471721 1711.41
.143 0101222010422150... 0 1011111111111... 1029417 2561883 234 148 26789789 13 81 12755153 213087.31
.146 0100222411133244... 0 1010111111111... 101025817 307166 236 1636 36376171044 3 3 597458 22444.39
.156 0110222441113224... 0 1101111111111... 100215 357 - 23 1032 2 3 243 25.19 349 3479 8
.16 0100122140142140... 0 0111111111111... 1253 13935 - 23 229790 7 837 21577 141.08 149459 105351 16
.161 0102102132132430... 0 0111111111111... 12489 23784 241 159 654608936497 14 429 119516 795.65
.162 0100223110422610... 0 0000000000000101... 101111111111111270580364 268435454 228 201307 261520645 63 24565333
.163 0102231042261042... 0 0001110111111... 100011122815290 262457212 228 48774 85082864 417 7050063 131228606 8262204.75
.164 0100122344511632... 0 0000011001111... 1100111112333838 45296885 229 20543 3402756 3 3 37070973 938684.36
.165 0102132134436231... 0 1101111111111... 1002(17#+87) - - 25 620 2 2 - - 1550 5181 4
.166 0100223411662244... 0 1011111111111... 102176 4281 241 181 18108192589123 3 15905 589.31
.167 0102234116224411... 0 1011111111111... 10260 1303 243 64 332129728 2 2 9407 161.03
.172 0110223011322440... 0 1011001111111... 11001022352 51381 238 392 268072142017 10 3947 192643 3893.11
.174 0110213221445642... 0 1101111111111... 100257 674 243 82 312784191354 2 3 13383 146.25
.204 0010120101231212... 1 0101110111111... 100010122245 83860 238 465 234528691963 - - 256102 3139.34
.205 0012010123123134... 1 1110010111111... 10110002112 33944004 243 94 1140389987762- - 81239243 113.73
.206 0010123201012323... 0 0011011111111... 10011210339 5668113 236 870 23409412874 19 5184 12259776 10652.60
.207 0012120301245312... 1 0110100111111... 11010012155 2174767600500241 128 341715359271 - - 917015 142.63
.224 0012012312314304... 0 0000001111111... 11111121633992 234975332 228 26371 56303768 26 198802 117487665 2858539.99
.244 0010123234515673... 0 1000111111111... 1110265367 7596617 231 7374 1032170197 3 3 11295819 240108.03
.245 0012123451567321... 0 0101111111111... 1012151 1352 242 146 20308285618812 1 87579 383.98
.264 0012345163251867... 0 1001111111111... 11021992 46544 238 1011 69651677642 2 1 426369 5796.45
.314 0120120212312453... 0 0000011111111... 111112180149 333219910 231 3589 170683843 56 2770 214048003 338938.17
.324 0102130134023421... 1 1110010111111... 10110002126 129608 242 113 642064155864 - - 487269 135.79
.334 0120120312312435... 0 0000100101111... 10110111123226764 262962276 228 33841 99297297 47 159618 131481137 6726442.24
.336 0120312403120341... 0 0011111111111... 112223 53899 241 101 843314440005 14 630 193967 852.74
.342 0101232010323450... 0 ? ? > 101355471 228 229385 268413453 68 636295
.344 0101232451462321... 0 0011111111111... 1128679 313574 235 1404 7241270191 2 2 535382 58700.00
.346 0101232451672321... 0 ? ? > 105245964 228 462549 268330658 2 2
.354 0120124312352435... 0 1111110111111... 10000002132 3227 - 113 1152 2 3 1613 68.70 1180 10061916 44
.356 0120212451675128... 0 1101111111111... 10027 43 - 19 86 2 3 19 11.07 142 7315 2
.36 0102102132132430... 0 0111111111111... 12516 11798 241 215 104286314112 14 429 32322 816.36
.362 0102341023415237... 0 0011111111111... 112529 43110 241 141 175951224651 11 227 328477885 1035.80
.364 0102132134534231... 0 1111011111111... 100002977 13573224 239 564 6784 2 2 129303688 1420.42
.366 0102345162345768... 0 0111111111111... 12827 643528 239 548 387241007404 2 2 1724483 2510.35
.37 0120123123403421... 0 0111011111111... 1000121583 20626 239 386 374602320656 13 407 1353583 2748.39
.371 0123103240234012... 0 0000001110111... 100011111121498349 48231695 228 17474 27626301 42 40891 26945025 3011034.80
.374 0120124312352435... 0 0111111111111... 12246 2354 241 237 846439142280 2 3 10961 584.89
.376 0120312435243514... 0 0111111111111... 12510 1140540 - 176 341612 2 3 570270 417.00 4 2268248 42
.404 0001122334115633... 0 1101101011111... 101001002369 8024 240 265 71029986654 7 286 5434066 1068.84
.414 0011022344011322... 0 ? ? > 111088039 228 935627 268293043 21 238588
.416 0011223411663221... 0 1010111111111... 101021014 10965 239 740 459561988878 3 16 14029 2794.73
.444 0001122334115633... 0 1101111111111... 1002364 72416309 241 233 949328477503 3 2 451989749 655.59
.45 0011223114432211... 0 1111111111111... 0211 198 - 8 37 2 1 37 12.80 20 498 8
.454 0011223411663221... 0 1011111111111... 10217 124 - 41 14456117 2 1 4858 64.64 60620715 160949019 16
.56 0102241132446621... 0 1101101111111... 100100246 1795 - 64 22778 2 2 7405 48.45 144 326640 26
.564 0102244113254768... 0 0110011111111... 1100121687 13275 238 1512 39104712026 2 2 24037 7144.23
.6 0012012312340342... 0 0111011111111... 1000121584 20627 239 386 374602320656 14 408 1353584 2749.39
.604 0012012312345345... 0 0000000011001... 110011111111235329942 268429931 228 655623 249869596 15 7943720
.606 0012340123451234... 0 0111111111111... 12112710 2147286993 231 1637 1018462325 18 732 1073643497 78666.78
.64 0012341532154268... 0 0111110111111... 10000012488 156751 239 262 1911635806 2 1 619865797 1089.33
.644 001234516325896a... 0 0111111111111... 1231 511 - 64 333 2 1 604 44.02 442 3256 32
.74 0101232414623215... 0 1101101111111... 10010021386 15929 239 512 76103606 2 2 395273 3760.74
.744 0101232451672321... 0 0011011111111... 100112876 11268 239 789 398831952222 2 2 62750 3970.95
.76 0102341623416732... 0 0000000110011... 110011111112219248 5208068 229 18320 298074788 2 2 7447283 921989.23
.764 0102345162345768... 0 0111001111111... 110001212078 941007 235 5465 33189838648 2 2 1963002 52443.71
.774 0123145671328954... 0 0101111111111... 1012352 3519 241 257 3285 1 0 183466 520.62
.776 0123416321674581... 0 1001111011111... 100001102503 7348 240 296 5487 1 0 302101968 635.16

4.004 0010123231454323... 0 0111111111111... 128914 43090760 235 2002 19690197206 3 3 33084859 23654.20
4.007 0012123454132825... 0 1111110101111... 10100000022259 186900 238 1024 183768341213 2 1 269541 6704.09
4.026 0012345613274165... 0 1000111111111... 11102611925 536869093 229 25813 505884464 2 1 268434547 1794307.07
4.044 0010123234541673... 0 0011111111111... 112184 1688 240 295 244301891602 3 3 21701 779.58
4.045 0012123454167828... 0 1111101111111... 100000234 497 243 99 44854535731752 1 5412 128.57
4.064 0012345613285764... 0 1101011111111... 10100252 470 - 111 19114 2 1 420 80.07 16132 94272 45
4.324 0120312435241352... 0 1110110111111... 10010002271 5956 240 259 635603736921 2 3 4734546568 740.12
4.327 0124312435213524... 0 1111111011111... 1000000027111 1084182 235 2247 7409767 1 0 1771014 21764.79
4.344 012021246164812a... 0 1110111111111... 1000214 271 - 35 190 2 3 164 20.59 51 998 4
4.364 0120312435243521... 0 0111111111111... 12(6#+992) - - 33 2141 2 3 - - 62 11687 14
4.367 0124312435213524... 0 0111111111111... 12142 3508 242 110 595251350570 1 0 272121 230.28
4.404 0012314324523513... 0 0111101111111... 1000012132 1852 - 208 229872163 2 1 17840 108.92 145 6872982644 71
4.406 0012345621874598... 0 1101111111111... 100223 205 - 50 231573 2 1 212 63.14 44 294097 32
4.44 0012341632167458... 0 1001111011111... 100001102504 7349 240 296 5488 2 1 302101969 636.16

.6111... 0012312341321461... 0 1011111111111... 102171 2026 243 78 582019050136 2 1 32009544 221.29

Grundy's0001021021021321... 0 0111111111111... 121287 48399022 239 297 21544358589 42 1222 51335130 3129.40
Couples 0001201231234034... 0 0111011111111... 1000121585 20628 239 386 374602320657 15 409 1353585 2750.39

# counts the number of considered periods. So, the number (default is 1) in front of the # is the number of rare values in a period.
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 the preceeding 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 (including the 3 duplicates for history).

Listing of these 93 nontrivial octal games with at most 3 places and 0.6111... and Grundy's Game sorted by

in the given examined domain.
The games 4.44, 0.04, 0.37 and Couples-are-forever are omitted in the preceeding 7 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
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 (<= last+t) of the mex-shift register to simulate the game after the last rare value has occured

Support

In July 2026, Tyler Satchel Orden from Los Angelos, USA, supports this database of octal games by extending the sgv-sequence of lots of octal games.
In October 2026, Udo Sprute from Lage, Germany, supports this database of octal games by writing a fast parallel C/OpenMP-program (with AVX2 support) to compute Nim-sequences.

Table 3 (with sortable columns): Nontrivial Octal Games with known Structure

Game period* preperiod* miss density excepttypebitmaskrare last+t max Gdepthper_depthaverageautocorrelsolved
.45 20 498 67 0.1345 80 0211 200 837 37 12.80001 0.4 1956
.156 349 3479 1919 0.5516 80 100215 360 23243 243 25.192066 0.8367 1967
.055 148 259 129 0.4980 20 026 46 820 20 12.973028 0.8378 1976
.644 442 3256 2208 0.6781320 1231 514 64604 46 44.0158207 0.7285 1976
.356 142 7315 6419 0.8775 20 10027 46 1919 19 11.070426 0.9155 1976
.165 1550 5181 251 0.0484 40 1002(17#+87) - 252597 - - 620 0.9277 1976
.127 4 46578 15622 0.3354111 1111102693 27109 5613551 0 0.0000- 0.0000 1988-10-??
.56 144 326640 291858 0.8935260 100100246 1797 647405 143 48.444459 0.6042 1988-10-??
.16 149459 105351 3634 0.0345160 1253 13937 2321577 21577 141.12053 0.9148 1988-10-??
.376 4 2268248 1104157 0.4868420 12510 1140543176570270254 417.0000- 0.0000 1988-10-??
.454 60620715 160949019 147240872 0.9148160 10217 127 414858 4362 64.637098 0.3424 2000-12-31
.104 11770282 197769598 163524206 0.8268 91 1000220 287 294178 1692 4.318012 0.4993 2001-07-01
.106 3282261404744653842637973624554558620.7788251 10010215 1106 3115343 14334 16.4416152 0.3548 2002-05-21
.054 10015179 193235616 170776546 0.8838180 10238 799 4116284 7070 103.5564108 0.5809 2002-05-27
.354 1180 10061916 7912461 0.7864440 10000002132 3230 1131613 301 63.0746193 0.7517 2012-10-??
4.064 16132 94272 88473 0.9385450 10100252 473 111420 325 80.06965 0.7894 2012-10-27
4.344 51 998 643 0.6443 40 1000214 274 35164 16 20.588220 0.9216 2012-10-27
4.364 62 11687 1198 0.1025140 12(6#+992) - 334221 - - 4 0.4839 2012-10-27
4.406 44 294097 258904 0.8803320 100223 208 50212 76 63.13647 0.5 2012-10-27
4.404 145 6872964789 6644376157 0.9667710 1000012132 1855 20817840 62 73.09663 0.8897 2012-10-29
*the length of the minimal (pre)period is given

To prove a period length p of 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 8 and 65 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 ultimately 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 a table of how fast n climbs for the next two power of all 3-place octal games.


A clickable image of maxi ≤ n G(i) of the strongest growing 3-place octal games for all n < 226.

The concept of sparse position space.

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

Further informations on the .00...007 = .0k-17 games

Table 4 (with sortable columns)

Game bitstringbitmaskrarelastmax nmax Gindexlostultimatedepthaverage

.0 17- -- -- 986∞- --
.0 2700011101111111... 1000111222476 5029983 2341691 2489029273716170 7845114 34011.46
.0 3700011111111111... 1112184853 158691802266279 50820531 31827065 11905098 411249.14
.0 47? ? > 53829398 22713184813391765392132461318
.0 5701111010111111... 1010000128052 596514 2261306 55169705 2126851 1105876 14706.72
.0 6700010011111111... 110111238988 67098670226946 41527950 202900 31361289 40637.46
.0 7701111110111101...100001000000128285490 671088082266293965955392 23930307
.0 8701111111111111... 124196 13699174226628 55881099 21602 11384172 4670.00
.0 9701111111111111... 1215942 786315 2261574 60249513 231943 719532 33819.04
.010701111101111111... 10000012631674 649041692261583714222362 254074 260156081358147.73
.011701111111011111... 1000000012344111 671085022263183 52619437 24809 31726124 215985.43
.012701111111111111... 129144 258184 226945 34886850 269456 399670 14787.70
.013701111110111111... 10000001218420 34417070226980 43727664 275437 24994325 33746.57
.014701111111011111... 10000000128954 6024150 2261216 27955191 285834 6081096 15516.99
.015701111111001111... 11000000012350462 519848982267555 13447593 296231 26989502 460987.68
.016700010010011111... 11011011127658383 671087332263283466335222 306628
.017701111111111111... 1260434 665111772262347 66219467 301223 32614784 74097.66
.018701111111111111... 12258199 671087552262440 845568 311292 2255931 128866.29
.019701111111111111... 1242430 4609107 2263039 36957497 33216131 3926588 88893.70
.020700000000111011...10001111111121084831 670907922261255165614777 3413930 324194011548309.49
.021701111101101111... 10010000012363821 654526072267876 33124115 341499 325333641132189.08
.022701111111111111... 1263803 2126833 2264096 4160051 3741646 1784010 124854.07
.023701111111101011...10100000000121167744 427197352261638443080033 3791185 172008611051846.96
.024701111111111111... 125089332 671078122264369460755237 371706
.025701111111111111... 12151523 638997852264482 33196754 381775 31137518 245392.62
.0267? ? > 46325096 2271474641327456026129392266
.027700010010001111... 11101101112205281 51702062267811 15854430 401913 4281668 399542.24
.028700000000000001...1111111111111211742010 671088332266554742743037 666019448
.0297? ? > 50027072 2271475761338315576184234995
.030700010010001111... 111011011123909752 655685642262458637281028 432120 165951424736023.02
.031701111111111001...110000000000123595507 671081052265314324742358 442189
Each game .0k-17 has Gk(i)=0 for all i < k; where k-1 counts the number of zeroes in the game-name, respectively k specifies the position of the 7 in the octal code of its game-name.
The first k-many zeroes of the Spargue-Grundy-function of the game we call the trivial lose-positions of the game.
Notice that for all k > 1; the game 0.0k-24 has the Spargue-Grundy-sequence as 0.0k-17 but shifted by one additional 0 at the start.
We conjecture: For each k > 3 and for all i with k < i ≤ k+12 let ji be the i-th lose position of the game, which always exists.
Then there are 12 positive, stricly increasing integers αi-k and 12 positive, increasing integers βi-k such that holds ji= αi-kk-βi-k.
We have (αh) = 3,5,9,13,17,21,29,33,41,49,65,69 and (βh)=1,1,3,5,5,7,9,11,11,13,19,19.
We have confirmed this conjecture numerically for all 3 < k < 32.
We call the game .0k-17 simple if it has exactly k+12 lose-positions. We conjecture that the sequence of the k of such simple games is 8,11,17,18,21,24,25,27,30,31,49,... . I.e. for all missing positive integers k, the corresponding nim-sequence of the game has more than 12+k lose-positions.

|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 1820 22 24 26 28 30 32 2k,  k>1
4 |14 15 20 25 30 35 40 4550 55 60 65 70 75 80 5k,  k>2
8 |69 55 75 95 115 135 155 17519521523525527529531520k-5,  k>2
16 |-154157190 230 270 310 35039043047051055059063040k-10,  k>4
32 |-434508437 530 617 673 7608479341021110811951282136987k-23,  k>7
64 |-13201521125711251309 146117751800196821782258243526132791 178k-57,  k>13
128|-32175894336826914588 490542575558512249214775549953825903
256|-91682233711776542519560179251645220650208981980712037244601171814724
512|-356626575831700158579199966730107983594026461710037343072704142947433142
1024|-1093621571858689474667-248642-177709159710445384--143411104694
2048|--450546325183- -    745402--4499291826020---498119
4096|--11927691123380- -    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

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 2026-11-17 12:38 UTC+1
Achim Flammenkamp