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, 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

Offset: 1

Author

Jennifer A. Moon & Kellen Myers, Jun 17 2016

Keywords

• nonn
• easy

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

Examples

			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.
		

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)

Crossrefs

Cf. A002187.

Programs

Mathematica

Union[{2, 3, 17, 37}, Flatten[Outer[Plus, {7, 11, 23, 27, 31}, 34 Range[0, 10]]]]

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

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