The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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. 2
 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 (list; graph; refs; listen; history; text; internal format)
 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 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 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified May 26 22:58 EDT 2020. Contains 334634 sequences. (Running on oeis4.)