A007705 -id:A007705 - cp's OEIS frontend

A123565 a(n) is the number of positive integers k which are <= n and where k, k-1 and k+1 are each coprime to n.

1, 0, 0, 0, 2, 0, 4, 0, 0, 0, 8, 0, 10, 0, 0, 0, 14, 0, 16, 0, 0, 0, 20, 0, 10, 0, 0, 0, 26, 0, 28, 0, 0, 0, 8, 0, 34, 0, 0, 0, 38, 0, 40, 0, 0, 0, 44, 0, 28, 0, 0, 0, 50, 0, 16, 0, 0, 0, 56, 0, 58, 0, 0, 0, 20, 0, 64, 0, 0, 0, 68, 0, 70, 0, 0, 0, 32, 0, 76, 0, 0, 0, 80, 0, 28, 0, 0, 0, 86, 0, 40, 0, 0

Offset: 1

Leroy Quet, Nov 12 2006

a(p) = p-3 for any odd prime p. a(2n) = a(3n) = 0.
a(n) > 0 if and only if n is coprime to 6. - Chai Wah Wu, Aug 26 2016
Multiplicative by the Chinese remainder theorem. - Andrew Howroyd, Aug 07 2018
From Eduard I. Vatutin, Nov 03 2020: (Start)
a(n) is the number of cyclic diagonal Latin squares of order n with the first row in order. Every cyclic diagonal Latin square is a cyclic Latin square, so a(n) <= A000010(n). Every cyclic diagonal Latin square is pandiagonal, but the converse is not true. For example, for order n=13 there is a square
   7  1  0  3  6  5 12  2  8  9 10 11  4
   2  3  4 10  0  7  6  9 12 11  5  8  1
   4 11  1  7  8  9 10  3  6  0 12  2  5
   6  5  8 11 10  4  7  0  1  2  3  9 12
   8  9  2  5 12 11  1  4  3 10  0  6  7
   3  6 12  0  1  2  8 11  5  4  7 10  9
  10  0  3  2  9 12  5  6  7  8  1  4 11
   1  7 10  4  3  6  9  8  2  5 11 12  0
  11  4  5  6  7  0  3 10  9 12  2  1  8
   5  8  7  1  4 10 11 12  0  6  9  3  2
  12  2  9  8 11  1  0  7 10  3  4  5  6
   9 10 11 12  5  8  2  1  4  7  6  0  3
   0 12  6  9  2  3  4  5 11  1  8  7 10
that is pandiagonal but not cyclic (Dabbaghian and Wu). (End)
Schemmel's totient function of order 3 (Schemmel, 1869; Sándor and Crstici, 2004). - Amiram Eldar, Nov 22 2020
a(p) is a lower bound for cardinality of clique of MODLS for all odd prime orders p: a(p) <= A328873(p). - Eduard I. Vatutin, Apr 02 2021
Also number of solutions for n-queens problem on toroidal chessboard (see A051906, A007705 or A370672), given by knight with (dx,dy) movement parameters starting from top left corner (more generally: from one cell fixed for all solutions). - Eduard I. Vatutin, Mar 13 2024

			The positive integers which are both coprime to 25 and are <= 25 are 1,2,3,4,6,7,8,9,11,12,13,14,16,17,18,19,21,22,23,24. Of these integers there are 10 integers k where (k-1) and (k+1) are also coprime to 25. These integers k are 2,3,7,8,12,13,17,18,22,23. So a(25) = 10.
Example of a cyclic diagonal Latin square of order 5:
  0 1 2 3 4
  2 3 4 0 1
  4 0 1 2 3
  1 2 3 4 0
  3 4 0 1 2
Example of a cyclic diagonal Latin square of order 7:
  0 1 2 3 4 5 6
  2 3 4 5 6 0 1
  4 5 6 0 1 2 3
  6 0 1 2 3 4 5
  1 2 3 4 5 6 0
  3 4 5 6 0 1 2
  5 6 0 1 2 3 4
From _Eduard I. Vatutin_, Mar 13 2024: (Start)
Example of a(5)=2 solutions for n-queens problem on toroidal chessboard, given by knight with (+1,+2) and (+1,+3) movement parameters starting from top left corner:
.
+-----------+ +-----------+
| Q . . . . | | Q . . . . |
| . . Q . . | | . . . Q . |
| . . . . Q | | . Q . . . |
| . Q . . . | | . . . . Q |
| . . . Q . | | . . Q . . |
+-----------+ +-----------+
.
Example of a(7)=4 solutions for n-queens problem on toroidal chessboard, given by knight with (+1,+2), (+1,+3), (+1,+4), (+1,+5) movement parameters starting from top left corner:
.
+---------------+ +---------------+ +---------------+ +---------------+
| Q . . . . . . | | Q . . . . . . | | Q . . . . . . | | Q . . . . . . |
| . . Q . . . . | | . . . Q . . . | | . . . . Q . . | | . . . . . Q . |
| . . . . Q . . | | . . . . . . Q | | . Q . . . . . | | . . . Q . . . |
| . . . . . . Q | | . . Q . . . . | | . . . . . Q . | | . Q . . . . . |
| . Q . . . . . | | . . . . . Q . | | . . Q . . . . | | . . . . . . Q |
| . . . Q . . . | | . Q . . . . . | | . . . . . . Q | | . . . . Q . . |
| . . . . . Q . | | . . . . Q . . | | . . . Q . . . | | . . Q . . . . |
+---------------+ +---------------+ +---------------+ +---------------+
(End)

József Sándor and Borislav Crstici, Handbook of Number theory II, Kluwer Academic Publishers, 2004, chapter 3, p. 276.

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Vahid Dabbaghian and Tiankuang Wu, Constructing non-cyclic pandiagonal Latin squares of prime orders, Journal of Discrete Algorithms, Vol. 30 (2015), pp. 70-77.
Colin Defant, On Arithmetic Functions Related to Iterates of the Schemmel Totient Functions, J. Int. Seq., Vol. 18 (2015), Article # 15.2.1.
A. Hedayat, A complete solution to the existence and nonexistence of Knut Vik designs and orthogonal Knut Vik designs, J. Comb. Theory, Ser. A 22(3) (1977) 331-337.
Victor Schemmel, Ueber relative Primzahlen, Journal für die reine und angewandte Mathematik, Vol. 70 (1869), pp. 191-192.
Eduard I. Vatutin, Enumerating cyclic Latin squares and Euler totient function calculating using them, High-performance computing systems and technologies, 2020, Vol. 4, No. 2, pp. 40-48. (in Russian)
Eduard I. Vatutin, Arranging of N queens on toroidal board and generating pandiagonal Latin squares using them (in Russian).
Index entries for sequences related to Latin squares and rectangles.

Cf. A000010, A007705, A051906, A058026, A206256, A241663, A328873, A370672.

f:= proc(n) local V,R;
  V:= map(igcd,[$1..n],n);
  R:= V[1..n-2] + V[2..n-1] + V[3..n];
  numboccur(3,R);
end proc:
f(1):= 1:
map(f, [$1..100]); # Robert Israel, Mar 15 2024

f[n_] := Length[Select[Range[n],GCD[ #, n] == 1 && GCD[ # - 1, n] == 1 && GCD[ # + 1, n] == 1 &]];Table[f[n], {n, 100}] (* Ray Chandler, Nov 19 2006 *)
Join[{1},Table[Count[Boole[Partition[CoprimeQ[Range[n],n],3,1]],{1,1,1}],{n,2,100}]] (* Harvey P. Dale, Apr 09 2017 *)
f[2, e_] := 0; f[p_, e_] := (p - 3)*p^(e - 1); a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Nov 22 2020 *)

a(n)=if(gcd(n,6)>1, return(0)); sum(k=1,n,gcd(k^3-k,n)==1) \\ Charles R Greathouse IV, Aug 26 2016

Multiplicative with a(2^e) = 0 and a(p^e) = (p-3)*p^(e-1) for odd primes p. - Amiram Eldar, Nov 22 2020
a(2*n+1) = A338562(n) / (2*n+1)!. - Eduard I. Vatutin, Apr 02 2021
Sum_{k=1..n} a(k) ~ c * n^2, where c = Product_{p prime} (1 - 3/p^2) = 0.125486... (A206256). - Amiram Eldar, Nov 18 2022
a(n) = A370672((n-1)/2) / n. - Eduard I. Vatutin, Mar 13 2024

Extended by Ray Chandler, Nov 19 2006

A006717 Number of ways of arranging 2n+1 nonattacking semi-queens on a (2n+1) X (2n+1) toroidal board.

Original entry on oeis.org

1, 3, 15, 133, 2025, 37851, 1030367, 36362925, 1606008513, 87656896891, 5778121715415, 452794797220965, 41609568918940625

Offset: 0

N. J. A. Sloane

Also the number of "good" permutations on 2n+1 elements [Novakovich]. - N. J. A. Sloane, Feb 22 2011
Also the number of transversals of a cyclic Latin square of order 2n+1 and the number of orthomorphisms of the cyclic group of order 2n+1. - Ian Wanless, Oct 07 2001
Also the number of complete mappings of a cyclic group of order 2n+1; also (2n+1) times the number of "standard" complete mappings of cyclic group of order 2n+1. - Jieh Hsiang, D. Frank Hsu and Yuh Pyng Shieh (arping(AT)turing.csie.ntu.edu.tw), May 08 2002
See A003111 for further information.
A very simple model using only addition mod n: Let i=index vector (0,1,..n-1) on any set of n distinct values, and j=index vector for the values after reordering. Then j = (i + d) mod n, where d is the vector of distances moved, and a(n) = number of reorderings that give an equidistributed set d (i.e., 1 instance of each distance moved). Since a(n)=0 for all even n, taking only odd n gives the sequence above - Ross Drewe, Sep 03 2017
All broken diagonals and antidiagonals of cyclic Latin square are transversals, so a(n) >= 2*n for all n > 1 for which cyclic Latin squares exist. - Eduard I. Vatutin, Mar 23 2022

Yuh Pyng Shieh, Jieh Hsiang and D. Frank Hsu, On the enumeration of Abelian k-complete mappings, vol. 144 of Congressus Numerantium, 2000, pp. 67-88.
Yuh Pyng Shieh, Partition Strategies for #P-complete problem with applications to enumerative combinatorics, PhD thesis, National Taiwan University, 2001.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
I. Vardi, Computational Recreations in Mathematica. Addison-Wesley, Redwood City, CA, 1991, p. 118.

Christian Carley, The Name Tag Problem, Mathematics Undergraduate Theses (Boise State University, 2019).
N. J. Cavenagh and I. M. Wanless, On the number of transversals in Cayley tables of cyclic groups, Disc. Appl. Math. 158 (2010), 136-146.
S. Eberhard, F. Manners, and R. Mrazovic, Additive Triples of Bijections, or the Toroidal Semiqueens Problem , arxiv:1510.05987, [math.CO], 2016.
Jieh Hsiang, YuhPyng Shieh, and YaoChiang Chen, Cyclic Complete Mappings Counting Problems, National Taiwan University 2014/8/21.
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013.
N. Yu. Kuznetsov, Using the Monte Carlo Method for Fast Simulation of the Number of "Good" Permutations on the SCIT-4 Multiprocessor Computer Complex, Cybernetics and Systems Analysis, January 2016, Volume 52, Issue 1, pp 52-57.
B. D. McKay, J. C. McLeod and I. M. Wanless, The number of transversals in a Latin square, Des. Codes Cryptogr., 40, (2006) 269-284.
D. Novakovic, Computation of the number of complete mappings for permutations, Cybernetics & System Analysis, No. 2, v. 36 (2000), pp. 244-247.
Kevin Pratt, Closed-Form Expressions for the n-Queens Problem and Related Problems, arXiv:1609.09585 [cs.DM], 2016.
D. S. Stones and I. M. Wanless, Compound orthomorphisms of the cyclic group, Finite Fields Appl. 16 (2010), 277-289.
Eric Weisstein's World of Mathematics, Queens Problem.

Cf. A003111, A007705.

k = 6; A = zeros(1,k); for i = 1:k; n = 2*i-1; x = [0: n-1]; allP = perms(x); T = size(allP,1); X = repmat(x, T, 1); Y = mod(X + allP, n); Y = sort(Y, 2); L = ~(sum(Y ~= X, 2)); A(i) = sum(L); end; A
% 1st 6 terms by testing all n! possible distance vectors
% Ross Drewe, Sep 03 2017

Suppose n is odd and let b(n)=a((n-1)/2). Then b(n) is odd; if n>3 and n is not 1 mod 3 then b(n) is divisible by 3n; b(n)=-2n mod n^2 in n is prime; b(n) is divisible by n^2 if n is composite; b(n) is asymptotically in between 3.2^n and 0.62^n n!. [Cavenagh, Wanless], [McKay, McLeod, Wanless], [Stones, Wanless] - Ian Wanless, Jul 30 2010
b(n) is asymptotic to e^(-1/2) n!^2/n^(n-1) [Eberhard, Manners, Mrazovic]. - Sam Spiro, Apr 16 2019; corrected by Sean Eberhard, Jul 21 2023
a(n) = (2*n+1) * A003111(n). - Andrew Howroyd, Sep 28 2020

More terms from Jieh Hsiang, D. Frank Hsu and Yuh Pyng Shieh (arping(AT)turing.csie.ntu.edu.tw), May 08 2002
a(12) added from A003111 by N. J. A. Sloane, Mar 29 2007
Definition clarified by Vaclav Kotesovec, Sep 16 2014

A071607 Number of strong complete mappings of the cyclic group Z_{2n+1}.

Original entry on oeis.org

1, 0, 2, 4, 0, 8, 348, 0, 8276, 43184, 0, 5602176, 78309000, 0, 20893691564, 432417667152, 0

Offset: 0

J. Hsiang, D. F. Hsu and Y. P. Shieh (arping(AT)turing.csie.ntu.edu.tw), Jun 03 2002

A strong complete mapping of a cyclic group (Z_n,+) is a permutation f(x) of Z_n such that f(0)=0 and that f(x)-x and f(x)+x are both permutations.
a(n) is the number of solutions of the toroidal n-queen problem (A007705) with 2n+1 queens and one queen in the top-left corner.
Also a(n) is the number of horizontally or vertically semicyclic diagonal Latin squares of order 2n+1 with the first row in ascending order. Horizontally semicyclic diagonal Latin square is a square where each row r(i) is a cyclic shift of the first row  r(0) by some value d(i) (see example). Vertically semicyclic diagonal Latin square is a square where each column c(i) is a cyclic shift of the first column  c(0) by some value d(i). Cyclic diagonal Latin squares (see A123565) fall under the definition of vertically and horizontally semicyclic diagonal Latin squares simultaneously, in this type of squares each row r(i) is obtained from the previous one r(i-1) using cyclic shift by some value d. Definition from A343867 includes this type of squares but not only it. - Eduard I. Vatutin, Jan 25 2022

			f(x)=2x in (Z_7,+) is a strong complete mapping of Z_7 since f(0)=0 and both f(x)-x (=x) and f(x)+x (=3x) are permutations of Z_7.
From _Eduard I. Vatutin_, Jan 25 2022: (Start)
Example of cyclic diagonal Latin square of order 13:
.
   0  1  2  3  4  5  6  7  8  9 10 11 12
   2  3  4  5  6  7  8  9 10 11 12  0  1  (d=2)
   4  5  6  7  8  9 10 11 12  0  1  2  3  (d=4)
   6  7  8  9 10 11 12  0  1  2  3  4  5  (d=6)
   8  9 10 11 12  0  1  2  3  4  5  6  7  (d=8)
  10 11 12  0  1  2  3  4  5  6  7  8  9  (d=10)
  12  0  1  2  3  4  5  6  7  8  9 10 11  (d=12)
   1  2  3  4  5  6  7  8  9 10 11 12  0  (d=1)
   3  4  5  6  7  8  9 10 11 12  0  1  2  (d=3)
   5  6  7  8  9 10 11 12  0  1  2  3  4  (d=5)
   7  8  9 10 11 12  0  1  2  3  4  5  6  (d=7)
   9 10 11 12  0  1  2  3  4  5  6  7  8  (d=9)
  11 12  0  1  2  3  4  5  6  7  8  9 10  (d=11)
.
Example of horizontally semicyclic diagonal Latin square of order 13:
.
   0  1  2  3  4  5  6  7  8  9 10 11 12
   2  3  4  5  6  7  8  9 10 11 12  0  1  (d=2)
   4  5  6  7  8  9 10 11 12  0  1  2  3  (d=4)
   9 10 11 12  0  1  2  3  4  5  6  7  8  (d=9)
   7  8  9 10 11 12  0  1  2  3  4  5  6  (d=7)
  12  0  1  2  3  4  5  6  7  8  9 10 11  (d=12)
   3  4  5  6  7  8  9 10 11 12  0  1  2  (d=3)
  11 12  0  1  2  3  4  5  6  7  8  9 10  (d=11)
   6  7  8  9 10 11 12  0  1  2  3  4  5  (d=6)
   1  2  3  4  5  6  7  8  9 10 11 12  0  (d=1)
   5  6  7  8  9 10 11 12  0  1  2  3  4  (d=5)
  10 11 12  0  1  2  3  4  5  6  7  8  9  (d=10)
   8  9 10 11 12  0  1  2  3  4  5  6  7  (d=8)
(End)
From _Eduard I. Vatutin_, Apr 09 2024: (Start)
Example of N-queens problem on toroidal board, N=2*2+1=5, a(2)=2, given by knight with (+1,+2) and (+1,+3) movement parameters starting from top left corner:
.
+-----------+ +-----------+
| Q . . . . | | Q . . . . |
| . . Q . . | | . . . Q . |
| . . . . Q | | . Q . . . |
| . Q . . . | | . . . . Q |
| . . . Q . | | . . Q . . |
+-----------+ +-----------+
.
Example of N-queens problem on toroidal board, N=2*3+1=7, a(3)=4, given by knight with (+1,+2), (+1,+3), (+1,+4), (+1,+5) movement parameters starting from top left corner:
.
+---------------+ +---------------+ +---------------+ +---------------+
| Q . . . . . . | | Q . . . . . . | | Q . . . . . . | | Q . . . . . . |
| . . Q . . . . | | . . . Q . . . | | . . . . Q . . | | . . . . . Q . |
| . . . . Q . . | | . . . . . . Q | | . Q . . . . . | | . . . Q . . . |
| . . . . . . Q | | . . Q . . . . | | . . . . . Q . | | . Q . . . . . |
| . Q . . . . . | | . . . . . Q . | | . . Q . . . . | | . . . . . . Q |
| . . . Q . . . | | . Q . . . . . | | . . . . . . Q | | . . . . Q . . |
| . . . . . Q . | | . . . . Q . . | | . . . Q . . . | | . . Q . . . . |
+---------------+ +---------------+ +---------------+ +---------------+
(End)

Anthony B. Evans,"Orthomorphism Graphs of Groups", vol. 1535 of Lecture Notes in Mathematics, Springer-Verlag, 1991.
Y. P. Shieh, J. Hsiang and D. F. Hsu, "On the enumeration of Abelian k-complete mappings", vol. 144 of Congressus Numerantium, 2000, pp. 67-88.

Jieh Hsiang, Yuh Pyng Shieh, and Yao Chiang Chen, Cyclic complete mappings counting problems, in PaPS: Problems and Problem Sets for ATP Workshop in conjunction with CADE-18 and FLoC 2002.
Jieh Hsiang, YuhPyng Shieh, and YaoChiang Chen, Cyclic Complete Mappings Counting Problems, National Taiwan University 2014/8/21.
D. Novakovic, Computation of the number of complete mappings for permutations, Cybernetics & System Analysis, No. 2, v. 36 (2000), pp. 244-247.
I. Rivin, I. Vardi and P. Zimmermann, The n-queens problem, Amer. Math. Monthly, 101 (1994), pp. 629-639.
Eduard I. Vatutin, About the horizontally and vertically semicyclic diagonal Latin squares enumeration (in Russian).
Eduard I. Vatutin, Special types of diagonal Latin squares, Cloud and distributed computing systems in electronic control conference, within the National supercomputing forum (NSCF - 2022). Pereslavl-Zalessky, 2023. pp. 9-18. (in Russian)
Index entries for sequences related to Latin squares and rectangles.

Cf. A007705, A051906, A123565, A338620, A342990, A343867.

a(n) = A007705(n) / (2*n+1).
a(n) = A342990(n) / (2*n+1)!. - Eduard I. Vatutin, Mar 10 2022
a(n) = A051906(2*n+1) / (2*n+1). - Eduard I. Vatutin, Apr 09 2024

a(15)-a(16) added using A007705 by Andrew Howroyd, May 07 2021

A051906 Number of ways of placing n nonattacking queens on an n X n toroidal chessboard.

Original entry on oeis.org

1, 0, 0, 0, 10, 0, 28, 0, 0, 0, 88, 0, 4524, 0, 0, 0, 140692, 0, 820496, 0, 0, 0, 128850048, 0, 1957725000, 0, 0, 0, 605917055356, 0, 13404947681712, 0, 0, 0

Offset: 1

Matthias Engelhardt, Dec 17 1999

The sequence has been computed up to n = 23 by Rivin, Vardi & Zimmermann, see p. 637 of their paper from 1994. Further terms were calculated by the submitter, Dec 17 1999 and Jan 11 2001.
a(n) is divisible by n.
Only terms indexed by odd numbers coprime to 3 are nonzero, therefore A007705(n) = a(2n+1) is the main entry. - M. F. Hasler, Jul 01 2019
From Eduard I. Vatutin, Nov 27 2023: (Start)
For n <= 11 all solutions can be found using a knight moving with some displacements dx and dy starting from some cell with coordinates (x,y): (x,y) -> (x+dx,y+dy) -> (x+2*dx,y+2*dy) -> ... -> (x,y) (all operations modulo n). For n >= 13 some solutions are same, but not all (see examples).
All solutions of n-queens problem on toroidal chessboard are also solutions of n-queens problem on classical chessboard; the converse is not true, so a(n) <= A000170(n).
(End)

			From _Eduard I. Vatutin_, Nov 27 2023: (Start)
n=5 (all 10 solutions are shown below):
+-----------+ +-----------+ +-----------+ +-----------+ +-----------+
| Q . . . . | | Q . . . . | | . Q . . . | | . Q . . . | | . . Q . . |
| . . Q . . | | . . . Q . | | . . . Q . | | . . . . Q | | Q . . . . |
| . . . . Q | | . Q . . . | | Q . . . . | | . . Q . . | | . . . Q . |
| . Q . . . | | . . . . Q | | . . Q . . | | Q . . . . | | . Q . . . |
| . . . Q . | | . . Q . . | | . . . . Q | | . . . Q . | | . . . . Q |
+-----------+ +-----------+ +-----------+ +-----------+ +-----------+
+-----------+ +-----------+ +-----------+ +-----------+ +-----------+
| . . Q . . | | . . . Q . | | . . . Q . | | . . . . Q | | . . . . Q |
| . . . . Q | | Q . . . . | | . Q . . . | | . Q . . . | | . . Q . . |
| . Q . . . | | . . Q . . | | . . . . Q | | . . . Q . | | Q . . . . |
| . . . Q . | | . . . . Q | | . . Q . . | | Q . . . . | | . . . Q . |
| Q . . . . | | . Q . . . | | Q . . . . | | . . Q . . | | . Q . . . |
+-----------+ +-----------+ +-----------+ +-----------+ +-----------+
n=7:
+---------------+
| Q . . . . . . |
| . . . Q . . . |
| . . . . . . Q |
| . . Q . . . . |
| . . . . . Q . |
| . Q . . . . . |
| . . . . Q . . |
+---------------+
n=11:
+-----------------------+
| Q . . . . . . . . . . |
| . . Q . . . . . . . . |
| . . . . Q . . . . . . |
| . . . . . . Q . . . . |
| . . . . . . . . Q . . |
| . . . . . . . . . . Q |
| . Q . . . . . . . . . |
| . . . Q . . . . . . . |
| . . . . . Q . . . . . |
| . . . . . . . Q . . . |
| . . . . . . . . . Q . |
+-----------------------+
n=13 (first example can be found using a knight moving from cell (1,1) with dx=1 and dy=2, second example can't be obtained in the same way):
+---------------------------+ +---------------------------+
| Q . . . . . . . . . . . . | | Q . . . . . . . . . . . . |
| . . Q . . . . . . . . . . | | . . Q . . . . . . . . . . |
| . . . . Q . . . . . . . . | | . . . . Q . . . . . . . . |
| . . . . . . Q . . . . . . | | . . . . . . Q . . . . . . |
| . . . . . . . . Q . . . . | | . . . . . . . . . . . Q . |
| . . . . . . . . . . Q . . | | . . . . . . . . . Q . . . |
| . . . . . . . . . . . . Q | | . . . . . . . . . . . . Q |
| . Q . . . . . . . . . . . | | . . . . . Q . . . . . . . |
| . . . Q . . . . . . . . . | | . . . Q . . . . . . . . . |
| . . . . . Q . . . . . . . | | . Q . . . . . . . . . . . |
| . . . . . . . Q . . . . . | | . . . . . . . Q . . . . . |
| . . . . . . . . . Q . . . | | . . . . . . . . . . Q . . |
| . . . . . . . . . . . Q . | | . . . . . . . . Q . . . . |
+---------------------------+ +---------------------------+
(End)

M. R. Engelhardt, A group-based search for solutions of the n-queens problem, Discr. Math., 307 (2007), 2535-2551.
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 62-63.
Kevin Pratt, Closed-Form Expressions for the n-Queens Problem and Related Problems, arXiv:1609.09585 [cs.DM], 2016.
I. Rivin, I. Vardi and P. Zimmermann, The n-queens problem, Amer. Math. Monthly, 101 (1994), 629-639.

See A007705, which is the main entry for this sequence.

Cf. A000170, A071607.

a(n) = A071607((n-1)/2) * n for odd n. - Eduard I. Vatutin, Nov 27 2023, corrected Apr 10 2024

Term a(31) added from A007705 by Vaclav Kotesovec, Aug 25 2012

A085801 Maximum number of nonattacking queens on an n X n toroidal board.

Original entry on oeis.org

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

Konrad Schlude, Jul 24 2003

Independence number of the queens' graph on toroidal n X n board. - Andrey Zabolotskiy, Dec 11 2016

			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.

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.

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.

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

(* 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 *)

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

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)

A172517 Number of ways to place 2 nonattacking queens on an n X n toroidal board.

Original entry on oeis.org

0, 0, 0, 32, 100, 288, 588, 1152, 1944, 3200, 4840, 7200, 10140, 14112, 18900, 25088, 32368, 41472, 51984, 64800, 79380, 96800, 116380, 139392, 165000, 194688, 227448, 264992, 306124, 352800, 403620, 460800, 522720, 591872, 666400, 749088, 837828

Offset: 1

Vaclav Kotesovec, Feb 05 2010

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
V. Kotesovec, Number of ways of placing non-attacking queens and kings on boards of various sizes
Index entries for linear recurrences with constant coefficients, signature (2,2,-6,0,6,-2,-2,1).

Cf. A007705, A036464.

CoefficientList[Series[- 4 x^3 (x^3 + 6 x^2 + 9 x + 8) / ((x - 1)^5 (x + 1)^3), {x, 0, 50}], x] (* Vincenzo Librandi, May 29 2013 *)
LinearRecurrence[{2,2,-6,0,6,-2,-2,1},{0,0,0,32,100,288,588,1152},40] (* Harvey P. Dale, Sep 22 2015 *)

a(n) = n^2*(n-2)^2/2 if n is even and a(n) = n^2*(n-1)(n-3)/2 if n is odd.
G.f.: -4*x^4*(x^3+6*x^2+9*x+8) / ((x-1)^5*(x+1)^3). - Colin Barker, Jan 09 2013
a(n) = 2*a(n-1)+2*a(n-2)-6*a(n-3)+6*a(n-5)-2*a(n-6)-2*a(n-7)+a(n-8). - Wesley Ivan Hurt, May 28 2021

A172518 Number of ways to place 3 nonattacking queens on an n X n toroidal board.

Original entry on oeis.org

0, 0, 0, 0, 100, 576, 2156, 7168, 17496, 41600, 82280, 161280, 280540, 486080, 774900, 1232896, 1844976, 2757888, 3933456, 5606400, 7699860, 10570560, 14081980, 18754560, 24365000, 31647616, 40258296, 51204608, 63979916

Offset: 1

Vaclav Kotesovec, Feb 05 2010

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
V. Kotesovec, Number of ways of placing non-attacking queens and kings on boards of various sizes
Index entries for linear recurrences with constant coefficients, signature (2,4,-10,-5,20,0,-20,5,10,-4,-2,1).

Cf. A047659, A007705, A172517.

CoefficientList[Series[- 4 x^4 (9 x^6 + 94 x^5 + 199 x^4 + 388 x^3 + 151 x^2 + 94 x + 25) / ((x - 1)^7 (x + 1)^5), {x, 0, 50}], x] (* Vincenzo Librandi, May 29 2013 *)
LinearRecurrence[{2,4,-10,-5,20,0,-20,5,10,-4,-2,1},{0,0,0,0,100,576,2156,7168,17496,41600,82280,161280},30] (* Harvey P. Dale, Dec 27 2014 *)

a(n) = n^2*(n-2)*(n-4)*(n^2-6*n+12)/6 if n is even and a(n) = n^2*(n-1)*(n-3)*(n^2-8*n+18)/6 if n is odd. - Vaclav Kotesovec, Jan 31 2010

G.f.: -4*x^5*(9*x^6+94*x^5+199*x^4+388*x^3+151*x^2+94*x+25) / ((x-1)^7*(x+1)^5). - Colin Barker, Jan 09 2013

A172519 Number of ways to place 4 nonattacking queens on an n X n toroidal board.

Original entry on oeis.org

0, 0, 0, 0, 50, 288, 2450, 16384, 62208, 233600, 638880, 1755072, 3901534, 8772176, 17051850, 33507328, 59175640, 105557904, 173570244, 287904000, 447885774, 702042000, 1044894554, 1565385984, 2247132500, 3244194304, 4519015596

Offset: 1

Vaclav Kotesovec, Feb 05 2010

Jinyuan Wang, Table of n, a(n) for n = 1..1000
Vaclav Kotesovec, Number of ways of placing non-attacking queens and kings on boards of various sizes
Index entries for linear recurrences with constant coefficients, signature (-1, 3, 6, 3, -9, -20, -11, 15, 40, 31, -15, -53, -50, 0, 50, 53, 15, -31, -40, -15, 11, 20, 9, -3, -6, -3, 1, 1).

Cf. A007705, A061994, A172517, A172518, A173775, A178722.

LinearRecurrence[{-1, 3, 6, 3, -9, -20, -11, 15, 40, 31, -15, -53, -50, 0, 50, 53, 15, -31, -40, -15, 11, 20, 9, -3, -6, -3, 1, 1},{0, 0, 0, 0, 0, 50, 288, 2450, 16384, 62208, 233600, 638880, 1755072, 3901534, 8772176, 17051850, 33507328, 59175640, 105557904, 173570244, 287904000, 447885774, 702042000, 1044894554, 1565385984, 2247132500, 3244194304, 4519015596},40] (* Harvey P. Dale, Apr 30 2018 *)

a(n) = (n^8/24 - n^7 + 245n^6/24 - 113n^5/2 + 2843n^4/16 - 593n^3/2 + 4757n^2/24) + (n^6/8 - 5n^5/2 + 305n^4/16 - 129n^3/2 + 629n^2/8)*(-1)^n + 8n^2*cos(2*Pi*n/3)/3 + 9n^2*cos(Pi*n/2)/2.
Recurrence: a(n) = -a(n-1) + 3a(n-2) + 6a(n-3) + 3a(n-4) - 9a(n-5) - 20a(n-6) - 11a(n-7) + 15a(n-8) + 40a(n-9) + 31a(n-10) - 15a(n-11) - 53a(n-12) - 50a(n-13) + 50a(n-15) + 53a(n-16) + 15a(n-17) - 31a(n-18) - 40a(n-19) - 15a(n-20) + 11a(n-21) + 20a(n-22) + 9a(n-23) - 3a(n-24) - 6a(n-25) - 3a(n-26) + a(n-27) + a(n-28), n >= 29. - Vaclav Kotesovec, Feb 09 2010
G.f.: -2*x^5*(287*x^22 + 5191*x^21 + 25616*x^20 + 105043*x^19 + 280800*x^18 + 651461*x^17 + 1186795*x^16 + 1925172*x^15 + 2611064*x^14 + 3190574*x^13 + 3337574*x^12 + 3161250*x^11 + 2574658*x^10 + 1891298*x^9 + 1175308*x^8 + 649556*x^7 + 291897*x^6 + 115771*x^5 + 34682*x^4 + 8835*x^3 + 1294*x^2 + 169*x + 25) / ((x - 1)^9*(x + 1)^7*(x^2 + 1)^3*(x^2 + x + 1)^3). - Colin Barker, Sep 21 2014

A342990 Number of horizontally or vertically semicyclic diagonal Latin squares of order 2n+1.

Original entry on oeis.org

1, 0, 240, 20160, 0, 319334400, 2167003238400, 0, 2943669154922496000, 5253122016055001088000, 0, 144827547726179682893168640000, 1214667347283206181421056000000000, 0, 184737047979495031539522261089255424000000, 3555700708206908663181998415125686517760000000, 0

Offset: 0

Eduard I. Vatutin, Jan 27 2022

Horizontally semicyclic diagonal Latin square is a square where each row r(i) is a cyclic shift of the first row r(0) by some value d(i) (see example). Vertically semicyclic diagonal Latin square is a square where each column c(i) is a cyclic shift of the first column c(0) by some value d(i). Cyclic diagonal Latin squares (see A338562) fall under the definition of vertically and horizontally semicyclic diagonal Latin squares simultaneously, in this type of squares each row r(i) is obtained from the previous one r(i-1) using cyclic shift by some value d. Definition from A343867 includes this type of squares but not only it.

			Example of cyclic diagonal Latin square of order 13:
   0  1  2  3  4  5  6  7  8  9 10 11 12
   2  3  4  5  6  7  8  9 10 11 12  0  1  (d=2)
   4  5  6  7  8  9 10 11 12  0  1  2  3  (d=4)
   6  7  8  9 10 11 12  0  1  2  3  4  5  (d=6)
   8  9 10 11 12  0  1  2  3  4  5  6  7  (d=8)
  10 11 12  0  1  2  3  4  5  6  7  8  9  (d=10)
  12  0  1  2  3  4  5  6  7  8  9 10 11  (d=12)
   1  2  3  4  5  6  7  8  9 10 11 12  0  (d=14 ==  1 (mod 13))
   3  4  5  6  7  8  9 10 11 12  0  1  2  (d=16 ==  3 (mod 13))
   5  6  7  8  9 10 11 12  0  1  2  3  4  (d=18 ==  5 (mod 13))
   7  8  9 10 11 12  0  1  2  3  4  5  6  (d=20 ==  7 (mod 13))
   9 10 11 12  0  1  2  3  4  5  6  7  8  (d=22 ==  9 (mod 13))
  11 12  0  1  2  3  4  5  6  7  8  9 10  (d=24 == 11 (mod 13))
Example of horizontally semicyclic diagonal Latin square of order 13:
   0  1  2  3  4  5  6  7  8  9 10 11 12
   2  3  4  5  6  7  8  9 10 11 12  0  1  (d=2)
   4  5  6  7  8  9 10 11 12  0  1  2  3  (d=4)
   9 10 11 12  0  1  2  3  4  5  6  7  8  (d=9)
   7  8  9 10 11 12  0  1  2  3  4  5  6  (d=7)
  12  0  1  2  3  4  5  6  7  8  9 10 11  (d=12)
   3  4  5  6  7  8  9 10 11 12  0  1  2  (d=3)
  11 12  0  1  2  3  4  5  6  7  8  9 10  (d=11)
   6  7  8  9 10 11 12  0  1  2  3  4  5  (d=6)
   1  2  3  4  5  6  7  8  9 10 11 12  0  (d=1)
   5  6  7  8  9 10 11 12  0  1  2  3  4  (d=5)
  10 11 12  0  1  2  3  4  5  6  7  8  9  (d=10)
   8  9 10 11 12  0  1  2  3  4  5  6  7  (d=8)

Eduard I. Vatutin, About the horizontally and vertically semicyclic diagonal Latin squares enumeration (in Russian).
E. I. Vatutin, Special types of diagonal Latin squares, Cloud and distributed computing systems in electronic control conference, within the National supercomputing forum (NSCF - 2022). Pereslavl-Zalessky, 2023. pp. 9-18. (in Russian)
Eduard I. Vatutin, Numerical formula between number of horizontally or vertically semicyclic diagonal Latin squares and number of toroidal n-queens problem solutions (in Russian).
Index entries for sequences related to Latin squares and rectangles.

Cf. A007705, A071607, A338562, A343867.

a(n) = A071607(n) * (2*n+1)!.

a(n) = A007705(n) * (2n)!. - Eduard I. Vatutin, Mar 15 2024

cp's OEIS Frontend

A123565 a(n) is the number of positive integers k which are <= n and where k, k-1 and k+1 are each coprime to n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A006717 Number of ways of arranging 2n+1 nonattacking semi-queens on a (2n+1) X (2n+1) toroidal board.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

MATLAB

Formula

Extensions

A071607 Number of strong complete mappings of the cyclic group Z_{2n+1}.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A051906 Number of ways of placing n nonattacking queens on an n X n toroidal chessboard.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A085801 Maximum number of nonattacking queens on an n X n toroidal board.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A172517 Number of ways to place 2 nonattacking queens on an n X n toroidal board.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A172518 Number of ways to place 3 nonattacking queens on an n X n toroidal board.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula