login
Sprague-Grundy values for Wythoff's game.
2

%I #20 Jan 29 2022 12:17:52

%S 0,1,2,2,0,1,3,4,5,6,4,5,3,2,7,5,3,4,0,6,8,6,7,8,1,9,10,3,7,8,6,9,0,1,

%T 4,5,8,6,7,10,1,2,5,3,4,9,10,11,12,8,7,13,14,15,16,10,11,9,8,13,12,0,

%U 15,16,17,14,11,9,10,7,12,14,2,13,17,6,18,15

%N Sprague-Grundy values for Wythoff's game.

%D E. R. Berlekamp, J. H. Conway and R. K. Guy, Winning Ways, Academic Press, NY, 2 vols., 1982, see p. 76.

%H Georg Fischer, <a href="/A317205/b317205.txt">Table of n, a(n) for n = 0..1274</a> (First 50 rows)

%H Uri Blass and Aviezri S. Fraenkel, <a href="https://doi.org/10.1016/0304-3975(90)90098-3">The Sprague-Grundy function for Wythoff's game</a>, Theoretical Computer Science 75.3 (1990): 311-333. See Table 2.

%H A. Dress, A. Flammenkamp and N. Pink, <a href="http://dx.doi.org/10.1006/aama.1998.0632">Additive periodicity of the Sprague-Grundy function of certain Nim games</a>, Adv. Appl. Math., 22, p. 249-270 (1999).

%H R. K. Guy, <a href="http://dx.doi.org/10.1007/978-1-4613-3554-2_9">The unity of combinatorics</a>, Proc. 25th Iranian Math. Conf, Tehran, (1994), Math. Appl 329 129-159, Kluwer Dordrecht 1995, Math. Rev. 96k:05001.

%H Gabriel Nivasch, <a href="http://www.msri.org/people/staff/levy/files/Book56/43nivasch.pdf">More on the Sprague-Grundy function for Wythoff’s game</a>, pages 377-410 in "Games of No Chance 3, MSRI Publications Volume 56, 2009. See Table 1.

%e Triangle begins as:

%e 0;

%e 1, 2;

%e 2, 0, 1;

%e 3, 4, 5, 6;

%e 4, 5, 3, 2, 7;

%e 5, 3, 4, 0, 6, 8;

%e 6, 7, 8, 1, 9, 10, 3;

%e 7, 8, 6, 9, 0, 1, 4, 5;

%t mex[list_] := mex[list] = Min[Complement[Range[0, Length[list]], list]];

%t move[Wnim, {a_, b_}] := move[Wnim, {a, b}] =

%t Union[Table[{i, b}, {i, 0, a - 1}], Table[{a, i}, {i, 0, b - 1}],

%t Table[{a - i, b - i}, {i, 1, Min[a, b]}]];

%t SpragueGrundy[game_, list_] := SpragueGrundy[game, list] =

%t mex[SpragueGrundy[game, #] & /@ move[game, list]];

%t t[n_, m_] := SpragueGrundy[Wnim, {n - 1, m - 1}]; (* so far copied from A004481 *)

%t Flatten[Table[t[n, m], {n, 12}, {m,1, n}]] (* _Georg Fischer_, Feb 22 2020 *)

%Y See A004481 for the full table.

%K nonn,tabl

%O 0,3

%A _N. J. A. Sloane_, Aug 07 2018

%E More terms from _Georg Fischer_, Feb 22 2020