A316629 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.

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, 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, 13, 3, 7, 2, 3, 9, 5, 3, 4, 5, 7, 4, 9, 7, 8, 9, 7, 8, 6, 9, 5, 10, 16, 5

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

Sequence in context: A257820 A159273 A021749 * A254175 A088916 A117966

Adjacent sequences: A316626 A316627 A316628 * A316630 A316631 A316632

Keyword

nonn

Author

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

Status

approved