A389689 Length of the longest possible eventual period of the win/lose state of a subtraction game where the largest element of the subtraction set is n.

2, 4, 6, 8, 10, 12, 22, 25, 28, 45, 54, 61, 76, 94, 168, 168, 204, 314, 309, 266, 444, 516, 446

Offset

1,1

Links

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

Ingo Althöfer and Jörg Bültermann, Superlinear period lengths in some subtraction games, Theoretical Computer Science, Volume 148, Issue 1, 1995, Pages 111-119.

Rui Yao, Python program

Formula

a(n) <= 2^n.

By Althöfer and Bültermann's paper, a(16n+1)>=56n^3+52n^2+9n+1 for 1<=n<=26. It is conjectured that a(38n+1) is superlinear using the subtraction set {n, 8n, 30n+1, 37n+1, 38n+1}.

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 (L, W, W, W), {2,3} has period 5 (L, L, W, W, W), {1,3} has period 2 (L, W) and {3} has period 6 (L, L, L, W, W, W) 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 win/loss sequence is L, W, L, W, W, L, W, L, W, W, W, (W, W, L, W, W, L, W, L, W, W, L).

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[
    Sign[SGList[s, 10*n^3]]], {s, (Union[#, {n}] &) /@
     Subsets[Range[n - 1]]}]

Prog

(Python) # See Links.

Crossrefs

Cf. A389690.

Sequence in context: A198186 A379294 A264984 * A389690 A194390 A187688

Adjacent sequences: A389686 A389687 A389688 * A389690 A389691 A389692

Keyword

nonn,more

Author

Rui Yao, Oct 10 2025

Status

approved