login
This site is supported by donations to The OEIS Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A002188 Sprague-Grundy values for Grundy's game.
(Formerly M0044 N0014)
4
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, 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, 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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,6

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.

Guy, R. K. and Smith, C. A. B.; The G-values of various games. Proc. Cambridge Philos. Soc. 52 (1956), 514-526. See Table 4.

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

Eric M. Schmidt, Table of n, a(n) for n = 0..10000

Achim Flammenkamp, Sprague-Grundy Values of Grundy's Game

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]

Gabriel Nivasch, The Sprague-Grundy theory of impartial games [broken link]

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

CROSSREFS

See A036685 for indices of zero terms.

Sequence in context: A025656 A194517 A110658 * A128313 A283486 A216607

Adjacent sequences:  A002185 A002186 A002187 * A002189 A002190 A002191

KEYWORD

nonn,easy,look,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Pab Ter (pabrlos(AT)yahoo.com), May 11 2004

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 20 12:32 EST 2019. Contains 319330 sequences. (Running on oeis4.)