|
|
A361457
|
|
Numbers k such that the first player has a winning strategy in the game described in the Comments.
|
|
0
|
|
|
3, 4, 6, 7, 8, 10, 11, 12, 14, 15, 16, 17, 19, 20, 21, 23, 24, 26, 27, 28, 29, 30, 33, 34, 35, 36, 37, 38, 40, 42
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
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.
|
|
LINKS
|
|
|
EXAMPLE
|
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.
a(3) = 6 is a term because the first player can remove {1, 2, 3}, and the second player has no possible move.
|
|
MAPLE
|
Filter:= proc(n) local G;
G:= proc(S) option remember; local nS, i, j, x, k;
nS:= nops(S);
for i from 1 to nS-1 do
for j from i+1 to nS do
x:= n-S[i]-S[j];
if x = 0 then if not G(S minus {S[i], S[j]}) then return true fi; break
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
else break
fi
od od;
false
end proc;
G({$1..n-1})
end proc:
select(Filter, [$1..40]);
|
|
MATHEMATICA
|
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]]];
|
|
PROG
|
(Python)
from functools import lru_cache
from itertools import chain, combinations as C
def t(s): return tuple(sorted(s))
def ok(n):
def m(S, n):
yield from (c for c in chain(C(S, 2), C(S, 3)) if sum(c) == n)
@lru_cache(maxsize=None)
def winning(S, n):
return not all(winning(t(set(S)-set(P)), n) for P in m(S, n))
return winning(tuple(range(1, n)), n)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|