A389690 Length of the longest possible eventual period of the Sprague-Grundy value of a subtraction game where the largest element of the subtraction set is n.

2, 4, 6, 8, 10, 12, 22, 25, 28, 58, 54, 87, 114, 144, 189, 336, 306, 456, 728, 1178, 1180, 4464

Offset

1,1

Links

Table of n, a(n) for n=1..22.

Rui Yao, Python program

Formula

a(n) <= (n+1)^n.

Example

For n=3, the possible subtraction sets are {1,2,3}, {2,3}, {1,3}, {3}. We can calculate that the {1,2,3} set has period 4 (0, 1, 2, 3), {2,3} has period 5 (0, 0, 1, 1, 2), {1,3} has period 2 (0, 1) and {3} has period 6 (0, 0, 0, 1, 1, 1) so the largest possible one is 6.
The eventual in the name means that the sequence may not be period at the first term. For example, if the subtraction set is {1,4,10} then the SG value sequence is 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 3, 2, 3, 0, 1, 3, (0, 1, 0, 1, 2, 0, 1, 2, 0, 1, 2).

Mathematica

mex[list_] := Module[{m = 0}, While[MemberQ[list, m], m++]; m];
SGList[s_List, n_] :=
 Module[{sg = Array[0 &, n + 1], i},
  For[i = 2, i <= n + 1, i++,
   sg[[i]] = mex@sg[[Select[i - s, # >= 1 &]]]; ];
  sg]
possibleperiod[s_List] := Length[FindTransientRepeat[s, 2][[2]]]
A[n_] :=
 Max@Table[
   possibleperiod[
    SGList[s, 10*n^3]], {s, (Union[#, {n}] &) /@
     Subsets[Range[n - 1]]}]

Prog

(Python) # See Links.

Crossrefs

Cf. A389689.

Sequence in context: A379294 A264984 A389689 * A194390 A187688 A334292

Adjacent sequences: A389687 A389688 A389689 * A389691 A389692 A389693

Keyword

nonn,more

Author

Rui Yao, Oct 10 2025

Status

approved