A361457 - OEIS

%I #18 May 22 2023 19:25:06

%S 3,4,6,7,8,10,11,12,14,15,16,17,19,20,21,23,24,26,27,28,29,30,33,34,

%T 35,36,37,38,40,42

%N Numbers k such that the first player has a winning strategy in the game described in the Comments.

%C The game starts with the numbers 1 to k-1. The two players alternate moves.  Each move consists of removing two or three numbers that sum to k.  The first player with no possible move loses.

%H D. S. et al, <a href="https://math.stackexchange.com/questions/4657470/colour-2-or-3-numbers-that-total-15/4657619#4657619">Colour 2 or 3 numbers that total 15</a>, Mathematics StackExchange, Mar. 2023.

%e 5 is not a term of the sequence because the first player does not have a winning strategy: the game starts with {1, 2, 3, 4}, the first player must remove either {1, 4} or {2, 3}, the second player removes the remaining two numbers, and the first player has no possible move.

%e a(3) = 6 is a term because the first player can remove {1, 2, 3}, and the second player has no possible move.

%p Filter:= proc(n) local G;

%p   G:= proc(S) option remember; local nS,i,j,x,k;

%p     nS:= nops(S);

%p     for i from 1 to nS-1 do

%p       for j from i+1 to nS do

%p         x:= n-S[i]-S[j];

%p         if x = 0 then if not G(S minus {S[i],S[j]}) then return true fi; break

%p         elif x > 0 then if member(x,S,'k') and k > j then if not G(S minus {S[i],S[j],x}) then return true fi fi

%p         else break

%p         fi

%p     od od;

%p     false

%p   end proc;

%p   G({$1..n-1})

%p end proc:

%p select(Filter, [$1..40]);

%t Filter[n_] := Module[{G}, G[S_] := G[S] = Module[{nS, i, j, x, k}, nS = Length[S]; For[i = 1, i <= nS-1, i++, For[j = i+1, j <= nS, j++, x = n-S[[i]]-S[[j]]; If[x == 0, If[!G[S ~Complement~ {S[[i]], S[[j]]}], Return@True]; Break[], If[x > 0, k = FirstPosition[S, x]; If[k != {} && k[[1]] > j, If[!G[S ~Complement~ {S[[i]], S[[j]], x}], Return@True]], Break[]]]]]; False]; G[Range[n-1]]];

%t Select[Range[30], Filter] (* _Jean-François Alcover_, May 12 2023, after _Robert Israel_ *)

%o (Python)

%o from functools import lru_cache

%o from itertools import chain, combinations as C

%o def t(s): return tuple(sorted(s))

%o def ok(n):

%o     def m(S, n):

%o         yield from (c for c in chain(C(S, 2), C(S, 3)) if sum(c) == n)

%o     @lru_cache(maxsize=None)

%o     def winning(S, n):

%o         return not all(winning(t(set(S)-set(P)), n) for P in m(S, n))

%o     return winning(tuple(range(1, n)), n)

%o print([k for k in range(1, 26) if ok(k)]) # _Michael S. Branicky_, May 19 2023

%K nonn,more

%O 1,1

%A _Robert Israel_, Mar 12 2023

%E a(30) from _Michael S. Branicky_, May 22 2023