login
A316781
a(n) is the Sprague-Grundy value of the Node-Kayles game played on the graph of n diamonds linked at vertices of degree three.
1
2, 1, 0, 3, 3, 1, 4, 2, 6, 5, 0, 2, 7, 1, 4, 3, 3, 1, 4, 7, 7, 5, 0, 2, 8, 4, 4, 6, 3, 1, 8, 7, 7, 5, 0, 2, 2, 1, 4, 6, 3, 1, 8, 2, 7, 5, 0, 2, 8, 1, 4, 6, 3, 1, 4, 2, 7, 5, 0, 2, 8, 1, 4, 6, 3, 1, 8, 7, 7, 5, 0, 2, 8, 1, 4, 6, 3, 1, 8, 2, 7, 5, 0, 2, 8, 1, 4, 6, 3, 1, 8, 2, 7
OFFSET
1,1
COMMENTS
The diamond graph can be constructed on the vertex set {1,2,3,4} with edge set {{1,2}, {1,3}, {1,4}, {2,3}, {3,4}}.
The graph of n linked diamonds has the vertex set {v_0, v_1, ..., v_n, u_1, u_2, ..., u_n, w_1, w_2, ..., w_n} and the edge set {{v_0, v_1}, {v_1, v_2}, ..., {v_{n-1}, v_n}, {v_0, u_1},{v_0, w_1}, {u_1, v_1},{w_1, v_1}, {v_1, u_2}, {v_1, w_2},{u_2, v_2}, {w_2, v_2},...,{v_{n-1}, u_n}, {v_{n-1}, w_n}, {u_n, v_n},{w_n, v_n}}.
In particular, each diamond D_i has vertices v_{i-1}, v_i, u_i, w_i and edges {v_{i-1}, v_i}, {v_{i-1}, u_i}, {v_{i-1}, w_i}, {v_i, u_i}, {v_i, w_i}.
From Wing Hong Tony Wong, Aug 14 2019: (Start)
Starting from the 69th term, this sequence is periodic with period 12. The 69th through 80th terms are 5, 0, 2, 8, 1, 4, 6, 3, 1, 8, 2, 7.
The sequence X(n), as defined in the Formula section, is identical to the sequence A286332, since the Node-Kayles game on the X graph, as defined in the Formula section, is equivalent to the Remove-a-Square game on 2 X n rectangles. (End)
REFERENCES
E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for Your Mathematical Plays Volume 1, A. K. Peters, 2001.
LINKS
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.
FORMULA
The Sprague-Grundy value of the Node-Kayles game on the graph of n linked diamonds, a(n), can be calculated recursively using the Sprague-Grundy values of the Node-Kayles game on two variants, K and X, of the linked diamond graph. We will denote these variant values as K(n) and X(n), and provide their recursive definition as well.
The K variant graph of n linked diamonds has the vertex set {v_0, v_1, ..., v_n, u_1, u_2, ..., u_n, u_{n+1}, w_1, w_2, ..., w_n, w_{n+1}} and the edge set {{v_0, v_1}, {v_1, v_2}, ..., {v_{n-1}, v_n}, {v_0, u_1}, {v_0, w_1}, {u_1, v_1}, {w_1, v_1}, {v_1, u_2}, {v_1, w_2}, {u_2, v_2}, {w_2, v_2},...,{v_{n-1}, u_n}, {v_{n-1}, w_n}, {u_n, v_n}, {w_n, v_n}, {v_n, u_{n+1}}, {v_n, w_{n+1}}}.
The X variant graph of n linked diamonds has the vertex set {v_0, v_1, ..., v_n, u_0, u_1, u_2, ..., u_n, u_{n+1}, w_0, w_1, w_2, ..., w_n, w_{n+1}} with edge set {{v_0, v_1}, {v_1, v_2}, ..., {v_{n-1}, v_n}, {u_0, v_0}, {w_0, v_0}, {v_0, u_1}, {v_0, w_1}, {u_1, v_1}, {w_1, v_1}, {v_1, u_2}, {v_1, w_2}, {u_2, v_2}, {w_2, v_2},...,{v_{n-1}, u_n}, {v_{n-1}, w_n}, {u_n, v_n}, {w_n, v_n}, {v_n, u_{n+1}}, {v_n, w_{n+1}}}.
In the following recursive formulae, "mex{}" is used to denote the "minimum-excluded nonnegative integer" and "(+)" represents the bitwise exclusive OR. To simplify the recursive formulae, we further define K(-2) = K(-1) = X(-2) = X(-1) = 0 and K(0) = X(0) = 2, which also serve as our base cases.
a(n) = mex { K(i-3) (+) K(n-i-1), K(j-2) (+) 1 (+) K(n-j-1) : 1 <= i <= n+1, 1 <= j <= n }.
K(n) = mex { K(i-3) (+) X(n-i-1), K(j-2) (+) 1 (+) X(n-j-1) : 1 <= i <= n+1, 1 <= j <= n+1 }.
X(n) = mex { X(i-3) (+) X(n-i-1), X(j-2) (+) 1 (+) X(n-j-1) : 1 <= i <= n+1, 0 <= j <= n+1 }.
EXAMPLE
For n=1, our recursive formulae yield
X(1) = mex { X(-2) (+) X(-1), X(-1) (+) X(-2), X(-2) (+) 1 (+) X(0), X(-1) (+) 1 (+) X(-1), X(0) (+) 1 (+) X(-2) } = mex { 0, 1, 3 } = 2,
K(1) = mex { K(-2) (+) X(-1), K(-1) (+) X(-2), K(-1) (+) 1 (+) X(-1), K(0) (+) 1 (+) X(-2) } = mex { 0, 1, 3 } = 2, and
a(1) = mex { K(-2) (+) K(-1), K(-1) (+) K(-2), K(-1) (+) 1 (+) K(-1) } = mex { 0, 1 } = 2.
MATHEMATICA
mex[S_] := Block[{i}, i = 0; While[MemberQ[S, i], i = i + 1]; i];
a = {}; b = {0, 0, 2}; c = {0, 0, 2}; nn = 1000;
Do[AppendTo[a,
mex[Join[Table[BitXor[b[[i]], b[[n - i + 2]]], {i, n + 1}],
Table[BitXor[b[[j + 1]], 1, b[[n - j + 2]]], {j, n}]]]];
AppendTo[b,
mex[Join[Table[BitXor[b[[i]], c[[n - i + 2]]], {i, n + 1}],
Table[BitXor[b[[j + 1]], 1, c[[n - j + 2]]], {j, n + 1}]]]];
AppendTo[c,
mex[Join[Table[BitXor[c[[i]], c[[n - i + 2]]], {i, n + 1}],
Table[BitXor[c[[j + 1]], 1, c[[n - j + 2]]], {j, 0, n + 1}]]]],
{n, nn}]
CROSSREFS
KEYWORD
nonn
EXTENSIONS
Corrected by Wing Hong Tony Wong, Aug 14 2019
STATUS
approved