A002188 - OEIS

%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