|
| |
|
|
A274161
|
|
Numbers n such that in the edge-delete game on the path P_{n} the first player does not have a winning strategy.
|
|
2
|
|
|
|
2, 3, 7, 11, 17, 23, 27, 31, 37, 41, 45, 57, 61, 65, 75, 79, 91, 95, 99, 109, 113, 125, 129, 133, 143, 147, 159, 163, 167, 177, 181, 193, 197, 201, 211, 215, 227, 231, 235, 245, 249, 261, 265, 269, 279, 283, 295, 299, 303, 313, 317, 329, 333, 337, 347, 351
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
The edge-delete game on the graph G is as follows: Two players alternate turns, permanently deleting one edge from G on each turn. The game ends when a vertex is isolated in what remains of G. The player whose deletion created the isolated vertex loses the game.
Here P_{n} refers to the path with n vertices, not n edges.
|
|
|
LINKS
|
Pratik Alladi, Neel Bhalla, Tanya Khovanova, Nathan Sheffield, Eddie Song, William Sun, Andrew The, Alan Wang, Naor Wiesel, Kevin Zhang Kevin Zhao, PRIMES STEP Plays Games, arXiv:1707.07201 [math.CO], 2017, Section 8.
|
|
|
FORMULA
|
The sequence consists of {2,3,17,37} along with all positive integers congruent to 7, 11, 23, 27, and 31 modulo 34.
a(n) = a(n-1) + a(n-5) - a(n-6) for n > 15. - Andrew Howroyd, Nov 11 2018
|
|
|
EXAMPLE
|
The number 7 is included because a path on 7 vertices has no winning strategy for player 1 (P1). Consider the edges labeled 1 through 6, left to right along the path. Without loss of generality, P1's first turn is 1, 2, or 3. P1 cannot delete 1 (an immediate loss). If P1 deletes 2, P2 deletes 4 or 5 to force an immediate loss on P1's next turn. If P1 deletes 3, P2 deletes 5 to force the loss.
|
|
|
MATHEMATICA
|
Union[{2, 3, 17, 37}, Flatten[Outer[Plus, {7, 11, 23, 27, 31}, 34 Range[0, 10]]]]
|
|
|
PROG
|
(PARI) a(n)=if(n<10, [2, 3, 7, 11, 17, 23, 27, 31, 37][n], [7, 11, 23, 27, 31][n%5+1] + (34*(n\5-1))); \\ Andrew Howroyd, Nov 11 2018
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
