|
|
A002188
|
|
Sprague-Grundy values for Grundy's game.
(Formerly M0044 N0014)
|
|
19
|
|
|
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.
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
|
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]
|
|
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';
|
|
CROSSREFS
|
See A036685 for indices of zero terms.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
More terms from Pab Ter (pabrlos(AT)yahoo.com), May 11 2004
|
|
STATUS
|
approved
|
|
|
|