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

Author

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

Keywords

• nonn

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

• 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