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,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

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

Sequence in context: A366682 A107921 A171760 * A023843 A153990 A154811

Adjacent sequences: A085798 A085799 A085800 * A085802 A085803 A085804

Keyword

easy,nonn

Author

Konrad Schlude, Jul 24 2003

Status

approved