A085801 Maximum number of nonattacking queens on an n X n toroidal board.
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, 25, 26, 29, 28, 31, 30, 31, 33, 35, 34, 37, 37, 37, 38, 41, 40, 43, 42, 43, 45, 47, 46, 49, 49, 49, 50, 53, 52, 55, 54, 55, 57, 59, 58, 61, 61, 61, 62, 65, 64, 67, 66
Offset: 1
Examples
Four non-attacking queens can be placed on a 6 X 6 toroidal board: ...... ..Q... ....Q. .Q.... ...Q.. ...... But five queens cannot. Hence a(6) = 4.
References
- 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.
Links
- Vincenzo Librandi, Table of n, a(n) for n = 1..1000
- Grant Cairns, Queens on Non-square Tori, El. J. Combinatorics, N6, 2001
- Eldar Fischer, Tomer Kotek, and Johann A. Makowsky, Application of Logic to Combinatorial Sequences and Their Recurrence Relations
- V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 751.
- P. Monsky, Problem E3162, Amer. Math. Monthly 96 (1989), 258-259.
- Konrad Schlude and Ernst Specker, Zum Problem der Damen auf dem Torus, Technical Report 412, Computer Science Department ETH Zurich, 2003.
Crossrefs
Programs
-
Mathematica
(* Explicit formula, based on an article by Monsky: *) 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 *) -
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); vector(60,n,round(a(n))) \\ Joerg Arndt, Dec 13 2010
Formula
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
From Andrey Zabolotskiy, Dec 11 2016: (Start)
a(n) = n if n = 1, 5, 7, 11 (mod 12);
a(n) = n-1 if n = 2, 10 (mod 12);
a(n) = n-2 otherwise.
(End)
Comments