OFFSET
1,4
COMMENTS
Independence number of the queens' graph on toroidal n X n board. - Andrey Zabolotskiy, Dec 11 2016
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.
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)
EXAMPLE
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.
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 *)
PROG
(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
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
Konrad Schlude, Jul 24 2003
STATUS
approved