

A316632


a(n) is the SpragueGrundy value of the NodeKayles game on the 3 X n lattice graph.


3



2, 1, 1, 0, 3, 3, 2, 2, 2, 3, 3, 5, 2, 4, 1, 3
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

The NodeKayles game on the 1 X n lattice graph (i.e., path) is equivalent to the Dawson's chess game and thus produces the same SpragueGrundy values as A002187.
The NodeKayles game on the 2 X n lattice graph (i.e., ladder graph) produces the SpragueGrundy values 1,0,1,0,1,0,..., which are periodic with period 2 (A000035).
The NodeKayles game on the 4 X n lattice graph produces the SpragueGrundy values 0,0,0,0,0,..., which are constantly 0 (A000004).


REFERENCES

E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for Your Mathematical Plays, Volume 1, A K Peters, 2001.


LINKS

Table of n, a(n) for n=1..16.
Sierra Brown, Spencer Daugherty, Eugene Fiorini, Barbara Maldonado, Diego ManzanoRuiz, Sean Rainville, Riley Waechter, and Tony W. H. Wong, Nimber Sequences of NodeKayles Games, J. Int. Seq., Vol. 23 (2020), Article 20.3.5.
Max Fan, Generalized NodeKayles calculator implemented in Rust
Riley S. Waechter, Python program


EXAMPLE

a(1) is the SpragueGrundy value of the NodeKayles game played on the 3 X 1 lattice graph, which is a path of length 3. Hence, a(1)=2, which is the third term in the sequence A002187.
a(2) is the SpragueGrundy value of the NodeKayles game played on the 3 X 2 lattice graph, which is a ladder with three rungs. The first player has two possible moves: to color the a corner vertex, which has degree 2, or to color a vertex with degree 3. If the player colors a vertex of degree 2, the resultant graph is a path of length 3. As mentioned before, the SpragueGrundy value of the NodeKayles game played on a path of length 3 is 2. If the player colors a vertex of degree 3, the resultant graph consists of two isolated vertices. The SpragueGrundy value of the NodeKayles game played on two isolated vertices is 0. Hence, a(2) = mex{0,2} = 1, where mex is the minimum excluded function.


PROG

(Rust) // See Fan link.  Max Fan, May 23 2021
(Haskell)
pickCoords n = sequence [[0, 1, 2], [0..n1]]
mex list = head (filter (`notElem` list) [0..(maximum list+1)])
checkAdj [x, y] [n, m] = not ((x==n && abs(ym) <= 1)  (y==m && abs (xn) <= 1))
nextMoves max history = filter (\move > null history  all (checkAdj move) history) (pickCoords max)
calcNimber max history  null (nextMoves max history) = 0  otherwise = mex (map (\move > calcNimber max (history ++ [move])) (nextMoves max history))
a316632 n = calcNimber n []  Max Fan, May 23 2021


CROSSREFS

Cf. A000004, A000035, A002187.
Sequence in context: A321914 A321746 A133830 * A111571 A051509 A124816
Adjacent sequences: A316629 A316630 A316631 * A316633 A316634 A316635


KEYWORD

nonn,more


AUTHOR

Sierra Brown, Spencer Daugherty, Eugene Fiorini, Barbara Maldonado, Sean E. Rainville, Riley S. Waechter, Wing Hong Tony Wong, Jul 13 2018


EXTENSIONS

a(14)a(16) from Max Fan, May 23 2021


STATUS

approved



