OFFSET
0,6
COMMENTS
Comments from Allan C. Wechsler, Mar 22 2025 (Start)
Grundy's game starts with a single heap of n tokens. A legal move consists of dividing a heap into two unequal parts. Since heaps of size 1 or 2 cannot be so divided, once the position has no heaps larger than 2, there are no legal moves, and according to the usual convention in such games, the first player who cannot move loses.
Note that Grundy's game is not an "octal game", because that formalism is not rich enough to capture the "unequal" splitting rule. (End)
REFERENCES
C. Berge, Graphs and Hypergraphs, North-Holland, 1973; p. 324.
R. K. Guy, Fair Game: How to play impartial combinatorial games, COMAP's Mathematical Exploration Series, 1989; see p. 96.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
David Cleaver, Table of n, a(n) for n = 0..20000 (first 10000 terms from Eric M. Schmidt)
David Cleaver, Table of n, a(n) for n = 0..200000
Achim Flammenkamp, Sprague-Grundy Values of Grundy's Game
Achim Flammenkamp, Sprague-Grundy Values of Grundy's Game [local cached copy, pdf only, with permission]
Daniel Gray, Analysis of the 2-Person Combinatorial Games Split-S-Nim and Chomp on 2 Rows, Ph. D. Dissertation, Florida Atlantic Univ. (2025) ProQuest 32166166.
P. M. Grundy, Mathematics and games, Eureka (The Archimedeans' Journal), No. 2, 1939, pp. 6-8. [Annotated scanned copy. My former colleague and coauthor Florence Jessie MacWilliams (nee Collinson), who was a student at Cambridge University in 1939, gave me this journal. - N. J. A. Sloane, Nov 17 2018]
Richard K. Guy and Cedric A. B. Smith, The G-values of various games, Proc. Cambridge Philos. Soc. 52 (1956), 514-526. See Table 4.
Gabriel Nivasch, The Sprague-Grundy theory of impartial games
Gabriel Nivasch, The Sprague-Grundy theory of impartial games [archived version]
Eric Weisstein's World of Mathematics, Grundy's Game
FORMULA
"Mike Guy has computed ten million values, but a discernible pattern remains elusive" [Guy, 1989]. - N. J. A. Sloane, Jan 03 2016
MATHEMATICA
mex[list_] := mex[list] = Min[Complement[Range[0, Length[list]], list]];
move[grundygame, list_] := move[grundygame, list] = Union@Flatten[Union[Table[ Sort@Join[Drop[list, {i}], {list[[i]] - j, j}], {i, Length[list]}, {j, Floor[(list[[i]] - 1)/2]}], Table[Sort@Join[Drop[list, {i}], {list[[i]] - j, j}], {i, Length[list]}, {j, Ceiling[(list[[i]] + 1)/2], list[[i]] - 1}]], 1];
SpragueGrundy[game_, list_] := SpragueGrundy[game, list] =
mex[SpragueGrundy[game, #] & /@ move[game, list]];
Table[SpragueGrundy[grundygame, {i}], {i, 0, 42}] (* Birkas Gyorgy, Apr 19 2011 *)
PROG
(C++)
#include <algorithm>
#include <array>
#include <iostream>
int main() {
constexpr int bound = 10000;
std::array<int, bound+1> gnumbers;
std::array<bool, bound/2+1> excluded;
for (int i = 0; i <= bound; ++i) {
auto e_begin = excluded.begin();
auto e_end = e_begin + i/2;
std::fill(e_begin, e_end, false);
for (int j = 1; j < (i+1)/2; ++j) {
int const k = i - j;
excluded[gnumbers[j] ^ gnumbers[k]] = true;
}
gnumbers[i] = std::find(e_begin, e_end, false) - e_begin;
}
for (int i = 0; i <= bound; ++i)
std::cout << i << ' ' << gnumbers[i] << '\n';
} // Eric M. Schmidt, Jan 04 2017
(Python)
def SpragueGrundy(bound):
gnumbers = [0 for i in range(bound+2)]
for i in range(bound+1):
excluded = [0 for z in range(i//2+1)]
for j in range(1, (i+1)//2):
k = i - j
excluded[gnumbers[j] ^ gnumbers[k]] = 1
gnumbers[i] = excluded.index(0)
return gnumbers[:-1]
print(SpragueGrundy(100)) # David Cleaver, Mar 22 2025
CROSSREFS
KEYWORD
AUTHOR
EXTENSIONS
More terms from Pab Ter (pabrlos(AT)yahoo.com), May 11 2004
STATUS
approved