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.

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

Author

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

Keywords

• nonn

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)

Examples

			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.
		

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.

Crossrefs

Cf. A002187, A286332, A316533, A316629, A316632.

Programs

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}]

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

Extensions

Corrected by Wing Hong Tony Wong, Aug 14 2019