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,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

Table of n, a(n) for n=1..93.

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

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

Sequence in context: A346038 A215062 A215063 * A290733 A113020 A347277

Adjacent sequences: A316778 A316779 A316780 * A316782 A316783 A316784

Keyword

nonn

Author

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

Extensions

Corrected by Wing Hong Tony Wong, Aug 14 2019

Status

approved