|
| |
|
|
A085801
|
|
Maximum number of nonattacking queens on an n X n toroidal board.
|
|
6
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
COMMENTS
|
Polya showed that a(n)=n if n is not divisible by 2 and not divisible by 3. Schlude and Specker showed the following: If n is even but not divisible by 3 and not divisible by 4, then a(n)=n-1. If n is divisible by 3, then a(n)<n-1. If n is divisible by 4 but not by 8, then a(n)<n-1. There are open questions as well: Does it hold that a(n)>n-3 for every n? Does it hold that a(n)<n-1 if n is divisible by 8?
According to the Cairns reference, it appears that the questions above were solved by Monsky. - Franklin T. Adams-Watters, Feb 06 2006
|
|
|
REFERENCES
|
Eldar Fischer, Tomer Kotek, and Johann A. Makowsky, Application of Logic to Combinatorial Sequences and Their Recurrence Relations, http://www.cs.technion.ac.il/~tkotek/pubfiles/12-FKM-final.pdf
G. Polya: Ueber 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
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
|
a(n) = n, if n is not divisible by 2 and not by 3. a(n) = n-1, if n is divisible by 2, but not by 3 and not by 4 a(n) < n-1, if n is divisible by 3
(Based on the first 1000 terms:) 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
|
|
|
EXAMPLE
|
a(5)=5 because 5 is not divisible by 2 and not divisible by 3
a(10)=10-1=9 because 10 is divisible by 2, but not by 3 and not by 4
a(12)=12-2=10 because 12 is divisible by 3
|
|
|
MATHEMATICA
|
(* Explicit formula, based on a 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.
Sequence in context: A102513 A100116 A107921 * A023843 A153990 A154811
Adjacent sequences: A085798 A085799 A085800 * A085802 A085803 A085804
|
|
|
KEYWORD
|
easy,nonn
|
|
|
AUTHOR
|
Konrad Schlude, Jul 24 2003
|
|
|
STATUS
|
approved
|
| |
|
|
