login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A085801 Maximum number of nonattacking queens on an n X n toroidal board. 9
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 (list; graph; refs; listen; history; text; internal format)
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: A100116 A107921 A171760 * A023843 A153990 A154811

Adjacent sequences:  A085798 A085799 A085800 * A085802 A085803 A085804

KEYWORD

easy,nonn

AUTHOR

Konrad Schlude, Jul 24 2003

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 19 12:09 EST 2019. Contains 320310 sequences. (Running on oeis4.)