login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

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

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 21 17:07 EST 2019. Contains 319350 sequences. (Running on oeis4.)