|
| |
|
|
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.
|
|
1
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
4,2
|
|
|
COMMENTS
|
a(n) is periodic with period 62 and final irregularity at n = 115 (proved).
A071461 gives Sprague-Grundy values for octal games .124 and .1241, where n=21 and n=49 differ.
|
|
|
REFERENCES
|
E. R. Berlekamp, J. H. Conway, and R. K. Guy, Winning Ways for Your Mathematical Plays, Volume 1, A K Peters, 2001.
|
|
|
LINKS
|
|
|
|
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]
|
|
|
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 *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
