login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Maximum number of nonattacking queens on an n X n toroidal board.
9

%I #48 Jan 01 2018 13:17:55

%S 1,1,1,2,5,4,7,6,7,9,11,10,13,13,13,14,17,16,19,18,19,21,23,22,25,25,

%T 25,26,29,28,31,30,31,33,35,34,37,37,37,38,41,40,43,42,43,45,47,46,49,

%U 49,49,50,53,52,55,54,55,57,59,58,61,61,61,62,65,64,67,66

%N Maximum number of nonattacking queens on an n X n toroidal board.

%C Independence number of the queens' graph on toroidal n X n board. - _Andrey Zabolotskiy_, Dec 11 2016

%D G. Polya: Über die 'Doppelt-Periodischen' Loesungen des n-Damen-Problems, in: W. Ahrens: Mathematische Unterhaltungen und Spiele, Teubner, Leipzig, 1918, 364-374. Reprinted in: G. Polya: Collected Works, Vol. V, 237-247.

%H Vincenzo Librandi, <a href="/A085801/b085801.txt">Table of n, a(n) for n = 1..1000</a>

%H Grant Cairns, <a href="http://www.combinatorics.org/Volume_8/Abstracts/v8i1n6.html">Queens on Non-square Tori</a>, El. J. Combinatorics, N6, 2001

%H Eldar Fischer, Tomer Kotek, and Johann A. Makowsky, <a href="http://www.cs.technion.ac.il/~tkotek/pubfiles/12-FKM-final.pdf">Application of Logic to Combinatorial Sequences and Their Recurrence Relations</a>

%H V. Kotesovec, <a href="https://oeis.org/wiki/User:Vaclav_Kotesovec">Non-attacking chess pieces</a>, 6ed, 2013, p. 751.

%H P. Monsky, <a href="http://www.jstor.org/stable/2325220">Problem E3162</a>, Amer. Math. Monthly 96 (1989), 258-259.

%H Konrad Schlude and Ernst Specker, <a href="https://doi.org/10.3929/ethz-a-006666110">Zum Problem der Damen auf dem Torus</a>, Technical Report 412, Computer Science Department ETH Zurich, 2003.

%F G.f.: (2*x^12 - x^11 + 2*x^10 + 2*x^9 + x^8 - x^7 + 3*x^6 - x^5 + 3*x^4 + x^3 + 1)/(x^13 - x^12 - x + 1) = (2*x^12 - x^11 + 2*x^10 + 2*x^9 + x^8 - x^7 + 3*x^6 - x^5 + 3*x^4 + x^3 + 1)/((x - 1)^2*(x + 1)*(x^2 + 1)*(x^2 - x + 1)*(x^2 + x + 1)*(x^4 - x^2 + 1)). - _Joerg Arndt_, Dec 13 2010

%F From _Andrey Zabolotskiy_, Dec 11 2016: (Start)

%F a(n) = n if n = 1, 5, 7, 11 (mod 12);

%F a(n) = n-1 if n = 2, 10 (mod 12);

%F a(n) = n-2 otherwise.

%F (End)

%e Four non-attacking queens can be placed on a 6 X 6 toroidal board:

%e ......

%e ..Q...

%e ....Q.

%e .Q....

%e ...Q..

%e ......

%e But five queens cannot. Hence a(6) = 4.

%t (* Explicit formula, based on an article by Monsky: *)

%t Table[n-1/6*(2*Cos[Pi*n/2]-3*Cos[Pi*n/3]+5*Cos[2*Pi*n/3]-Cos[Pi*n/6]-Cos[5*Pi*n/6]+3*Cos[Pi*n]+7),{n,1,100}] (* _Vaclav Kotesovec_, Dec 13 2010 *)

%o (PARI) a(n)=n-1/6*(2*cos(Pi*n/2)-3*cos(Pi*n/3)+5*cos(2*Pi*n/3)-cos(Pi*n/6)-cos(5*Pi*n/6)+3*cos(Pi*n)+7);

%o vector(60,n,round(a(n))) \\ _Joerg Arndt_, Dec 13 2010

%Y Cf. A051906, A007705, A279402, A279404, A279405, A172517, A172518, A172519, A173775, A178722.

%K easy,nonn

%O 1,4

%A _Konrad Schlude_, Jul 24 2003