cp's OEIS Frontend

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

%I A085801 #48 Jan 01 2018 13:17:55
%S A085801 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 A085801 25,26,29,28,31,30,31,33,35,34,37,37,37,38,41,40,43,42,43,45,47,46,49,
%U A085801 49,49,50,53,52,55,54,55,57,59,58,61,61,61,62,65,64,67,66
%N A085801 Maximum number of nonattacking queens on an n X n toroidal board.
%C A085801 Independence number of the queens' graph on toroidal n X n board. - _Andrey Zabolotskiy_, Dec 11 2016
%D A085801 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 A085801 Vincenzo Librandi, <a href="/A085801/b085801.txt">Table of n, a(n) for n = 1..1000</a>
%H A085801 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 A085801 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 A085801 V. Kotesovec, <a href="https://oeis.org/wiki/User:Vaclav_Kotesovec">Non-attacking chess pieces</a>, 6ed, 2013, p. 751.
%H A085801 P. Monsky, <a href="http://www.jstor.org/stable/2325220">Problem E3162</a>, Amer. Math. Monthly 96 (1989), 258-259.
%H A085801 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 A085801 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 A085801 From _Andrey Zabolotskiy_, Dec 11 2016: (Start)
%F A085801 a(n) = n if n = 1, 5, 7, 11 (mod 12);
%F A085801 a(n) = n-1 if n = 2, 10 (mod 12);
%F A085801 a(n) = n-2 otherwise.
%F A085801 (End)
%e A085801 Four non-attacking queens can be placed on a 6 X 6 toroidal board:
%e A085801 ......
%e A085801 ..Q...
%e A085801 ....Q.
%e A085801 .Q....
%e A085801 ...Q..
%e A085801 ......
%e A085801 But five queens cannot. Hence a(6) = 4.
%t A085801 (* Explicit formula, based on an article by Monsky: *)
%t A085801 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 A085801 (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 A085801 vector(60,n,round(a(n))) \\ _Joerg Arndt_, Dec 13 2010
%Y A085801 Cf. A051906, A007705, A279402, A279404, A279405, A172517, A172518, A172519, A173775, A178722.
%K A085801 easy,nonn
%O A085801 1,4
%A A085801 _Konrad Schlude_, Jul 24 2003