|
%I #41 Sep 25 2023 14:49:50
%S 0,1,3,4,2,3,1,2,0,4,6,5,7,3,2,7,6,2,0,2,1,3,2,4,3,5,0,3,1,2,10,1,11,
%T 2,1,9,7,8,4,9,5,3,1,2,7,4,9,7,6,9,7,8,4,3,5,2,6,5,10,4,9,14,0,4,11,8,
%U 13,3,7,2,3,9,5,3,4,5,7,4,9,7,8,9,7,8,6,9,5,10,16,5
%N a(n) is the Sprague-Grundy value of the Node-Kayles game on the semi-regular graph of 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, u_1, u_2, ..., u_n, and u_{n+1} 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.
%C 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.
%D E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for Your Mathematical Plays, Volume 1, A K Peters, 2001.
%H Sean E. Rainville, <a href="/A316629/b316629.txt">Table of n, a(n) for n = 1..110949</a>
%H Sierra Brown, Spencer Daugherty, Eugene Fiorini, Barbara Maldonado, Diego Manzano-Ruiz, Sean Rainville, Riley Waechter, and Tony W. H. Wong, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL23/Wong/wong24.html">Nimber Sequences of Node-Kayles Games</a>, J. Int. Seq., Vol. 23 (2020), Article 20.3.5.
%H Sean E. Rainville, <a href="/A316629/a316629.txt">Python program for A316629</a>
%F We define b(n) and c(n), as well as their recurrence relations, to be used in the recurrence relation for a(n).
%F 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.
%F 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.
%F In the following recurrence relations, '+' is the bitwise XOR operator.
%F Recurrence relation for a(n):
%F 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.
%F Initial conditions for a(n): a(1)=0, a(2)=1, a(3)=3.
%F Recurrence relation for b(n):
%F 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)}
%F Initial conditions for b(n): b(0)=2, b(1)=1, b(2)=3, b(3)=2, b(4)=5.
%F Recurrence relation for c(n):
%F 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))}
%F Note that c(-1), for convenience, refers to the Sprague-Grundy value of the Node-Kayles game on the path graph on two vertices.
%F Initial conditions for c(n): c(-1)=1, c(0)=3, c(1)=0, c(2)=1.
%e 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.
%o (Python) # See Rainville link.
%K nonn
%O 1,3
%A _Sierra Brown_, _Spencer Daugherty_, _Eugene Fiorini_, _Barbara Maldonado_, _Sean E. Rainville_, _Riley S. Waechter_, _Wing Hong Tony Wong_, Jul 13 2018
|
