A316781 - OEIS

%I #43 Jul 06 2020 22:30:24

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

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

%U 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

%N 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.

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

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

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

%C From _Wing Hong Tony Wong_, Aug 14 2019: (Start)

%C 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.

%C 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)

%D E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for Your Mathematical Plays Volume 1, A. K. Peters, 2001.

%H Sierra Brown, Spencer Daugherty, Eugene Fiorini, Barbara Maldonado, Diego Manzano-Ruiz, Sean Rainville, Riley Waechter, and Tony W. H. Wong, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL23/Wong/wong24.html">Nimber Sequences of Node-Kayles Games</a>, J. Int. Seq., Vol. 23 (2020), Article 20.3.5.

%F 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.

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

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

%F 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.

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

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

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

%e For n=1, our recursive formulae yield

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

%e 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

%e a(1) = mex { K(-2) (+) K(-1), K(-1) (+) K(-2), K(-1) (+) 1 (+) K(-1) } = mex { 0, 1 } = 2.

%t mex[S_] := Block[{i}, i = 0; While[MemberQ[S, i], i = i + 1]; i];

%t a = {}; b = {0, 0, 2}; c = {0, 0, 2}; nn = 1000;

%t Do[AppendTo[a,

%t   mex[Join[Table[BitXor[b[[i]], b[[n - i + 2]]], {i, n + 1}],

%t     Table[BitXor[b[[j + 1]], 1, b[[n - j + 2]]], {j, n}]]]];

%t AppendTo[b,

%t   mex[Join[Table[BitXor[b[[i]], c[[n - i + 2]]], {i, n + 1}],

%t     Table[BitXor[b[[j + 1]], 1, c[[n - j + 2]]], {j, n + 1}]]]];

%t AppendTo[c,

%t   mex[Join[Table[BitXor[c[[i]], c[[n - i + 2]]], {i, n + 1}],

%t     Table[BitXor[c[[j + 1]], 1, c[[n - j + 2]]], {j, 0, n + 1}]]]],

%t {n, nn}]

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

%K nonn

%O 1,1

%A _Sierra Brown_, _Spencer Daugherty_, _Eugene Fiorini_, _Barbara Maldonado_, _Sean E. Rainville_, _Riley S. Waechter_, _Wing Hong Tony Wong_, Jul 06 2018

%E Corrected by _Wing Hong Tony Wong_, Aug 14 2019