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.
a(n)-1 gives the zeros in the nim-sequence of octal game .4, see A002187. - Zachary Winkeler, Jul 10 2016
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..1000
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.
R. P. Gallant, G. Gunther, B. L. Hartnell, D. F. Rall, A game of edge removal on graphs, JCMCC, 57 (2006), 75 - 82.
Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,1,-1)
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
Jennifer A. Moon & Kellen Myers, Jun 17 2016
STATUS
approved