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

Georg Fischer, Table of n, a(n) for n = 4..996 (first 300 terms from Eugene Fiorini)

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

Cf. A071461.

Sequence in context: A127139 A309103 A166139 * A071431 A277322 A182740

Adjacent sequences: A317364 A317365 A317366 * A317368 A317369 A317370

Keyword

nonn

Author

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

Extensions

Edited by N. J. A. Sloane, Jan 30 2019

More terms from Eugene Fiorini, May 14 2019

Status

approved