OFFSET
1,3
COMMENTS
A similar graph is given by n linked 4-cycles with vertex set {u_1, u_2, ..., u_n, u_{n+1}, v_1, w_1, v_2, w_2, ..., v_n, w_n}. In this graph, edges are given by {u_i, v_i}, {u_i, w_i}, {v_i, u_{i+1}}, and {w_i, u_{i+1}} for all i=1,2,...,n. The Sprague-Grundy value of the Node-Kayles game played on this graph is 0 if n is odd and 1 otherwise.
REFERENCES
E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for Your Mathematical Plays, Volume 1, A K Peters, 2001.
LINKS
Sean E. Rainville, Table of n, a(n) for n = 1..110949
Sierra Brown, Spencer Daugherty, Eugene Fiorini, Barbara Maldonado, Diego Manzano-Ruiz, Sean Rainville, Riley Waechter, and Tony W. H. Wong, Nimber Sequences of Node-Kayles Games, J. Int. Seq., Vol. 23 (2020), Article 20.3.5.
Sean E. Rainville, Python program for A316629
FORMULA
We define b(n) and c(n), as well as their recurrence relations, to be used in the recurrence relation for a(n).
Let b(n) be the Sprague-Grundy value of the Node-Kayles game on the graph of n linked 4-cycles with vertex set {u_1, u_2, ..., u_n, u_{n+1}, u_{n+2}, u_{n+3}, v_1, w_1, v_2, w_2, ..., v_n, w_n}. In this graph, u_1, u_2, ..., u_n, u_{n+1}, u_{n+2}, and u_{n+3} form a path, and additional edges are given by {u_i, v_i}, {v_i, w_i}, and {w_i, u_{i+1}} for all i=1,2,...,n.
Let c(n) be the Sprague-Grundy value of the Node-Kayles game on the graph of n linked 4-cycles with vertex set {u_{-1}, u_0, u_1, u_2, ..., u_n, u_{n+1}, u_{n+2}, u_{n+3}, v_1, w_1, v_2, w_2, ..., v_n, w_n}. In this graph, u_{-1}, u_0, u_1, u_2, ..., u_n, u_{n+1}, u_{n+2}, and u_{n+3} form a path, and additional edges are given by {u_i, v_i}, {v_i, w_i}, and {w_i, u_{i+1}} for all i=1,2,...,n.
In the following recurrence relations, '+' is the bitwise XOR operator.
Recurrence relation for a(n):
a(n) = mex{a(n-1), a(n-2)+b(0), a(n-3)+b(1), ..., a(1)+b(n-3), b(n-3), b(n-2)+1, b(n-4)+b(0), b(n-5)+b(1), ..., b(n-4-floor((n-4)/2))+b(floor((n-4)/2))}, where mex is the minimum excluded function.
Initial conditions for a(n): a(1)=0, a(2)=1, a(3)=3.
Recurrence relation for b(n):
b(n) = mex{a(n), a(n-1)+c(-1), b(n-1), b(n-2), c(n-2)+1, c(n-3), a(1)+c(n-3), a(n-2)+c(0), a(n-3)+c(1), ..., a(2)+c(n-4), b(n-2)+b(0), b(n-3)+b(1), ..., b(floor((n-1)/2))+b(n-2-floor((n-1)/2)), b(n-3)+c(-1), b(n-4)+c(0), b(0)+c(n-4), b(1)+c(n-5), ..., b(n-5)+c(1)}
Initial conditions for b(n): b(0)=2, b(1)=1, b(2)=3, b(3)=2, b(4)=5.
Recurrence relation for c(n):
c(n) = mex{c(n-2), b(n-1)+c(-1), b(n), c(n-1), b(n-2)+c(0), b(n-3)+c(1), ..., b(floor(n/2))+c(n-2-floor((n-2)/2)), c(n-3)+c(-1), c(n-4)+c(0), ..., c(floor((n-3)/2))+c(n-4-floor((n-3)/2))}
Note that c(-1), for convenience, refers to the Sprague-Grundy value of the Node-Kayles game on the path graph on two vertices.
Initial conditions for c(n): c(-1)=1, c(0)=3, c(1)=0, c(2)=1.
EXAMPLE
For n=4, a(4)=mex{a(3), a(2)+b(0), a(1)+b(1), b(1), b(2)+1, b(0)+b(0)}=mex{3, 1, 2, 0}=4.
PROG
(Python) # See Rainville link.
CROSSREFS
KEYWORD
nonn
AUTHOR
STATUS
approved