The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A215721 The values of N for which the 1 X N domino-covering game is a second player win. 1
 0, 1, 5, 9, 15, 21, 25, 29, 35, 39, 43, 55, 59, 63, 73, 77, 89, 93, 97, 107, 111, 123, 127, 131, 141, 145, 157, 161, 165, 175, 179, 191, 195, 199, 209, 213, 225, 229, 233 (list; graph; refs; listen; history; text; internal format)
 OFFSET 1,3 COMMENTS In a domino-covering game, the players take turns placing dominoes (1 X 2 rectangles) on the board (here a 1 X N rectangle), such that the position of the dominoes is integer, and no two dominoes overlap. The loser is the first player unable to move. The optimal strategies for this game can be determined by computing the nim-value nv(N) of each board 1 X N: nv(0) = 0 nv(1) = 0 nv(N+2) = least nonnegative integer not in {nimsum(nv(k),nv(N-k)) : k <= N} (where nimsum(a,b) is the bitwise xor of a and b). The second player wins a game iff its nim-value is 0. LINKS Charles R Greathouse IV, Table of n, a(n) for n = 1..10000 Pratik Alladi, Neel Bhalla, Tanya Khovanova, Nathan Sheffield, Eddie Song, William Sun, Andrew The, Alan Wang, Naor Wiesel, and Kevin Zhang Kevin Zhao, PRIMES STEP Plays Games, arXiv:1707.07201 [math.CO], 2017, Section 8. Stephan Brumme, Project Euler.net Problem 306, (2017). Randal E. Bryant and Marijn J. H. Heule, Dual Proof Generation for Quantified Boolean Formulas with a BDD-Based Solver, Carnegie Mellon Univ. (2021). Index entries for linear recurrences with constant coefficients, signature (1,0,0,0,1,-1). FORMULA For n > 14, a(n) = a(n-5) + 34. - Rainer Rosenthal and Charles R Greathouse IV, Sep 20 2012 G.f.: x^2*(6*x^13 - 2*x^12 + 8*x^10 - 2*x^9 - 2*x^8 + 2*x^7 + 3*x^5 + 6*x^4 + 6*x^3 + 4*x^2 + 4*x + 1) / ((x - 1)^2*(x^4 + x^3 + x^2 + x + 1)). - Colin Barker, Jan 26 2013 EXAMPLE N=1: the first player is unable to move (second player win). N=2,3: any move by the first player renders the second player unable to move (first player win). N=4: the first player can win by covering the two central squares (first player win). N=5: any move by the first player has a final counter-move by the second (second player win). MATHEMATICA Rest@ CoefficientList[Series[x^2*(6 x^13 - 2 x^12 + 8 x^10 - 2 x^9 - 2 x^8 + 2 x^7 + 3 x^5 + 6 x^4 + 6 x^3 + 4 x^2 + 4 x + 1)/((x - 1)^2*(x^4 + x^3 + x^2 + x + 1)), {x, 0, 39}], x] (* Michael De Vlieger, Aug 18 2021 *) PROG (Python) import numpy as np N = np.array([0, 0]) U = np.arange(1000) for i in U:     N = np.append(N, np.setdiff1d(U, np.bitwise_xor(N[:-1], N[-2::-1])).min()) print(list(*np.where(N==0))) (PARI) a(n)=if(n<10, [0, 1, 5, 9, 15, 21, 25, 29, 35][n], n\5*34-[29, 25, 13, 9, 5][n%5+1]) \\ Charles R Greathouse IV, Aug 24 2012 (PARI) list(lim)=my(v=vector(lim\1+1), u); for(n=0, #v-3, u=vecsort(vector(n\2+1, k, bitxor(v[k], v[n-k+2])), , 8); for(i=0, #u-1, if(u[i+1]!=i, v[n+3]=i; next(2)); v[n+3]=#u)); for(i=0, #v-1, v[i+1]=if(v[i+1], 1, i)); vecsort(v, , 8) \\ Charles R Greathouse IV, Aug 24 2012 CROSSREFS The nim-values are A002187(n-1). Sequence in context: A315072 A315073 A315074 * A315075 A315076 A350472 Adjacent sequences:  A215718 A215719 A215720 * A215722 A215723 A215724 KEYWORD nonn,easy AUTHOR Yuval Gabay, Aug 22 2012 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified July 6 11:37 EDT 2022. Contains 355110 sequences. (Running on oeis4.)