%I M0044 N0014 #56 Nov 12 2020 16:53:21
%S 0,0,0,1,0,2,1,0,2,1,0,2,1,3,2,1,3,2,4,3,0,4,3,0,4,3,0,4,1,2,3,1,2,4,
%T 1,2,4,1,2,4,1,5,4,1,5,4,1,5,4,1,0,2,1,0,2,1,5,2,1,3,2,1,3,2,4,3,2,4,
%U 3,2,4,3,2,4,3,2,4,3,2,4,5,2,4,5,2,4,3,7,4,3,7,4,3,7,4,3,5,2,3,5,2,3,5,2,3
%N Sprague-Grundy values for Grundy's game.
%D C. Berge, Graphs and Hypergraphs, North-Holland, 1973; p. 324.
%D R. K. Guy, Fair Game: How to play impartial combinatorial games, COMAP's Mathematical Exploration Series, 1989; see p. 96.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Eric M. Schmidt, <a href="/A002188/b002188.txt">Table of n, a(n) for n = 0..10000</a>
%H Achim Flammenkamp, <a href="http://wwwhomes.uni-bielefeld.de/achim/grundy.html"> Sprague-Grundy Values of Grundy's Game</a>
%H P. M. Grundy, <a href="/A002188/a002188.pdf">Mathematics and games</a>, 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]
%H Richard K. Guy and Cedric A. B. Smith, <a href="https://doi.org/10.1017/S0305004100031509">The G-values of various games</a>, Proc. Cambridge Philos. Soc. 52 (1956), 514-526. See Table 4.
%H Gabriel Nivasch, <a href="http://www.gabrielnivasch.org/fun/combinatorial-games/sprague-grundy"> The Sprague-Grundy theory of impartial games</a>
%H Gabriel Nivasch, <a href="http://web.archive.org/web/20070504194337/yucs.org/~gnivasch/cgames/spraguegrundy/index.html">The Sprague-Grundy theory of impartial games</a> [archived version]
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GrundysGame.html">Grundy's Game</a>
%F "Mike Guy has computed ten million values, but a discernible pattern remains elusive" [Guy, 1989]. - _N. J. A. Sloane_, Jan 03 2016
%t mex[list_] := mex[list] = Min[Complement[Range[0, Length[list]], list]];
%t 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];
%t SpragueGrundy[game_, list_] := SpragueGrundy[game, list] =
%t mex[SpragueGrundy[game, #] & /@ move[game, list]];
%t Table[SpragueGrundy[grundygame, {i}], {i, 0, 42}] (* _Birkas Gyorgy_, Apr 19 2011 *)
%o (C++)
%o #include <algorithm>
%o #include <array>
%o #include <iostream>
%o int main() {
%o constexpr int bound = 10000;
%o std::array<int, bound+1> gnumbers;
%o std::array<bool, bound/2+1> excluded;
%o for (int i = 0; i <= bound; ++i) {
%o auto e_begin = excluded.begin();
%o auto e_end = e_begin + i/2;
%o std::fill(e_begin, e_end, false);
%o for (int j = 1; j < (i+1)/2; ++j) {
%o int const k = i - j;
%o excluded[gnumbers[j] ^ gnumbers[k]] = true;
%o }
%o gnumbers[i] = std::find(e_begin, e_end, false) - e_begin;
%o }
%o for (int i = 0; i <= bound; ++i)
%o std::cout << i << ' ' << gnumbers[i] << '\n';
%o } // _Eric M. Schmidt_, Jan 04 2017
%Y See A036685 for indices of zero terms.
%K nonn,easy,look,nice
%O 0,6
%A _N. J. A. Sloane_
%E More terms from Pab Ter (pabrlos(AT)yahoo.com), May 11 2004