A317367 Sprague-Grundy values for the Node-Kayles game played on the scalloped graph where vertices that are 3 away from each other are connected.
0, 2, 1, 3, 0, 1, 1, 3, 0, 2, 3, 3, 2, 2, 3, 4, 2, 4, 0, 4, 2, 5, 3, 2, 2, 3, 3, 2, 0, 3, 1, 1, 0, 3, 1, 2, 0, 3, 1, 2, 0, 1, 1, 4, 0, 4, 5, 4, 7, 2, 6, 4, 7, 5, 0, 4, 1, 1, 0, 2, 1, 3, 0, 2, 1, 3, 0, 1, 1, 3, 0, 2, 3, 3, 2, 2, 7, 4, 6, 5, 4, 4, 5, 5, 7, 2, 6, 3, 3, 2, 0, 3, 1, 1, 0, 3, 1, 2, 0, 3, 1, 2, 0, 1, 1
Offset: 4
Keywords
References
- E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for Your Mathematical Plays, Volume 1, A K Peters, 2001.
Links
- Georg Fischer, Table of n, a(n) for n = 4..996 (first 300 terms from Eugene Fiorini)
Crossrefs
Cf. A071461.
Programs
-
Mathematica
mex[S_] := Block[{i}, i=0; While[MemberQ[S,i], i=i+1]; i]; c={1}; Do[c = Append[c, mex[ Join[ {c[[n-2]]}, Table[ BitXor[ c[[i]], c[[n-3-i]] ], {i, Ceiling[(n-4)/2]} ] ] ] ], {n,2,1000}]; b={0}; Do[b = Append[b, mex[ Join[ {b[[n-2]]}, Table[ BitXor[ c[[i]], b[[n-3-i]] ], {i, n-4} ] ] ] ], {n,2,1000}]; a={}; Do[a = Append[a, mex[ Table[ BitXor[ b[[i]], b[[n-3-i]] ], {i, Ceiling[(n-4)/2]} ] ] ], {n,1000}]; (* Eugene Fiorini, May 14 2019 *)
Formula
Note that mex is the minimum excluded function and (+) is bitwise exclusive or. This is an obvious construction given the symmetry of the graph. We define a three-connected path graph P_{n}(3) as the path graph P_{n} with vertices labeled sequentially from 1 to n and additional edges E'={{i, j} : |i-j|=3}. The Sprague-Grundy value of P_{n}(3) is given by the function a(n).
The B-Variant of length n of P_{n}(3) (denoted P_{n}^{B}(3)) is exactly P_{n}(3) with one additional vertex -1 and one additional edge {-1,2}. The degree of vertex -1 is one. The Sprague-Grundy value of P_{n}^{B}(3) is given by the function b(n).
The C-Variant of length n of P_{n}(3) (denoted P_{n}^{C}(3)) is exactly P_{n}(3) with two additional vertices -1 and n+2 and additional edges {-1,2} and {n-1,n+2}. The degree of vertices -1 and n+2 is one. The Sprague-Grundy value of P_{n}^{C}(3) is given by the function c(n).
Then
a(n) = mex({b(i) (+) b(n-7-i) : -3 <= i <= ceiling(n/2)-4});
b(n) = mex({b(n-2)} union {c(i) (+) b(n-7-i): -3 <= i <= n-4});
c(n) = mex({c(n-2)} union {c(i) (+) c(n-7-i): -3 <= i <= ceiling(n/2)-4}). [Edited and extended by Eugene Fiorini, May 14 2019]
Extensions
Edited by N. J. A. Sloane, Jan 30 2019
More terms from Eugene Fiorini, May 14 2019
Comments