A338562 -id:A338562 - 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

A287648 Maximum number of diagonal transversals in a diagonal Latin square of order n.

Original entry on oeis.org

1, 0, 0, 4, 5, 6, 27, 120, 333

Offset: 1

Eduard I. Vatutin, May 29 2017

From Eduard I. Vatutin, Oct 04 2020: (Start)
A diagonal Latin square is a Latin square in which both the main diagonal and main antidiagonal contain each element.
A diagonal transversal is a transversal that includes exactly one element from the main diagonal and exactly one from the antidiagonal. For squares of odd orders, these elements can coincide at the intersection of the diagonals. (End)
A007016 is an upper bound for the number of diagonal transversals in a Latin square: A287647(n) <= a(n) <= A007016(n). - Eduard I. Vatutin, Jan 02 2020
a(11) >= 4828, a(12) >= 24901, a(13) >= 131106, a(14) >= 364596, a(15) >= 389318. - Natalia Makarova, Tomáš Brada, Harry White, Oct 04 2020
a(16) >= 32172800, a(18) >= 280308432. - Natalia Makarova, Tomáš Brada, Dec 25 2020
a(12) >= 28496. - Natalia Makarova, Harry White, Jan 23 2021
a(14) >= 380718, a(20) >= 90010806304, a(21) >= 51162162017, a(22) >= 3227747329246. The number of D-transversals for orders 20 - 22 was calculated by a volunteer. - Natalia Makarova, Tomáš Brada, Harry White, Mar 17 2021
All cyclic diagonal Latin squares (see A338562) are diagonal Latin squares, so A342997((n-1)/2) <= a(n). - Eduard I. Vatutin, Apr 26 2021
a(14) >= 383578, a(15) >= 398974. - Natalia Makarova, Tomáš Brada, Jan 13 2022
a(10) >= 890, a(12) >= 30192, a(14) >= 490218, a(15) >= 4620434, a(17) >= 204995269, a(18) >= 281593874, a(19) >= 11254190082. - Eduard I. Vatutin, Jul 22 2020, updated Mar 01 2025
For most orders n, at least one diagonal Latin square with the maximal number of diagonal transversals has an orthogonal mate and a(n) = A360220(n). Known exceptions: n=6 and n=10. - Eduard I. Vatutin, Feb 17 2023

			For example, the diagonal Latin square
  0 1 2 3
  3 2 1 0
  1 0 3 2
  2 3 0 1
has 4 diagonal transversals:
  0 . . .    . 1 . .    . . 2 .    . . . 3
  . . 1 .    . . . 0    3 . . .    . 2 . .
  . . . 2    . . 3 .    . 0 . .    1 . . .
  . 3 . .    2 . . .    . . . 1    . . 0 .
In addition there are 4 other transversals that are not diagonal transversals and are therefore not included here.
From _Natalia Makarova_, Oct 04 2020: (Start)
The following DLS of order 14 has 364596 diagonal transversals:
   0  7  6 11  9  3  4  5  2 12 13  8 10  1
   6  1 11  5 10 12  2  3  9  7  4 13  0  8
   5 11  2 12  8  1  7 10  0  6  9  3 13  4
  13  6  5  3  1 10  9 12  7  0  2  4  8 11
  12  3 10  1  4 13  8  6 11  5  0  7  2  9
  10 12  1  8  2  5 11 13  4  3  6  0  9  7
   9  2  7  0  5 11  6  8 13  4  1 10  3 12
   4 13  3  9  6  0 10  7  1  8 12  2 11  5
   2  4  9 10 11  6  1  0  8 13  7 12  5  3
   1 10  8 13 12  2  5  4  3  9 11  6  7  0
   3  5 12  7 13  8  0  1  6 11 10  9  4  2
   8  0 13  4  7  9  3  2 12 10  5 11  1  6
   7  9  0  6  3  4 13 11  5  2  8  1 12 10
  11  8  4  2  0  7 12  9 10  1  3  5  6 13
(End)

J. W. Brown, F. Cherry, L. Most, M. Most, E. T. Parker, and W. D. Wallis, Completion of the spectrum of orthogonal diagonal Latin squares, Lecture notes in pure and applied mathematics. 1992. Vol. 139. pp. 43-49.

Tomáš Brada, Top 10 CF-ODLK with most orthogonal mates
Natalia Makarova, Most perfect diagonal Latin square of order 9 with 333 diagonal transversals
Natalia Makarova, ODLS of order n>10
Natalia Makarova, DLS with maximum of D-transversals
Natalia Makarova, DLS of orders n = 11 - 22 with known maximum of D-transversals
Natalia Makarova, Spectrum by D-transversals for the 14th order DLS
Natalia Makarova, Spectrum by D-transversals for the 15th order DLS
E. I. Vatutin, Discussion about properties of diagonal Latin squares at forum.boinc.ru (in Russian).
Eduard I. Vatutin, Enumerating the Main Classes of Cyclic and Pandiagonal Latin Squares, Recognition - 2021, pp. 77-79. (in Russian)
Eduard Vatutin, Alexey Belyshev, Natalia Nikitina, Maxim Manzuk, Alexander Albertian, Ilya Kurochkin, Alexander Kripachev, and Alexey Pykhtin, Diagonalization and Canonization of Latin Squares, Supercomputing, Russian Supercomputing Days (RuSCDays 2023) Rev. Selected Papers Part II, LCNS Vol. 14389, Springer, Cham, 48-61.
E. I. Vatutin, S. E. Kochemazov, and O. S. Zaikin, Estimating of combinatorial characteristics for diagonal Latin squares, Recognition — 2017 (2017), pp. 98-100 (in Russian).
Eduard I. Vatutin, Stepan E. Kochemazov, Oleg S. Zaikin, Maxim O. Manzuk, Natalia N. Nikitina, and Vitaly S. Titov, Central symmetry properties for diagonal Latin squares, Problems of Information Technology (2019) No. 2, 3-8.
E. I. Vatutin, S. E. Kochemazov, O. S. Zaikin, and S. Yu. Valyaev, Enumerating the Transversals for Diagonal Latin Squares of Small Order, CEUR Workshop Proceedings. Proceedings of the Third International Conference BOINC-based High Performance Computing: Fundamental Research and Development (BOINC:FAST 2017). Vol. 1973. Technical University of Aachen, Germany, 2017. pp. 6-14. urn:nbn:de:0074-1973-0.
E. I. Vatutin, S. E. Kochemazov, O. S. Zaikin, and S. Yu. Valyaev, Using Volunteer Computing to Study Some Features of Diagonal Latin Squares, Open Engineering. Vol. 7. Iss. 1. 2017. pp. 453-460. DOI: 10.1515/eng-2017-0052.
E. I. Vatutin, S. E. Kochemazov, O. S. Zaikin, S. Yu. Valyaev, and V. S. Titov, Estimating the Number of Transversals for Diagonal Latin Squares of Small Order, Telecommunications. 2018. No. 1. pp. 12-21 (in Russian).
E. I. Vatutin, About the upper bound of number of diagonal transversals for diagonal Latin squares of order 10 (in Russian).
E. I. Vatutin, About the upper bound of number of diagonal transversals for diagonal Latin squares of order 9 (in Russian).
Eduard I. Vatutin, Natalia N. Nikitina, and Maxim O. Manzuk, First results of an experiment on studying the properties of DLS of order 9 in the volunteer distributed computing projects Gerasim@Home and RakeSearch (in Russian).
E. I. Vatutin, N. N. Nikitina, M. O. Manzuk, A. M. Albertyan, I. I. Kurochkin, On the construction of spectra of fast-computable numerical characteristics for diagonal Latin squares of small order, Intellectual and Information Systems (Intellect - 2021). Tula, 2021. pp. 7-17. (in Russian)
E. I. Vatutin, V. S. Titov, A. I. Pykhtin, A. V. Kripachev, N. N. Nikitina, M. O. Manzuk, A. M. Albertyan and I. I. Kurochkin, Estimation of the Cardinalities of the Spectra of Fast-computable Numerical Characteristics for Diagonal Latin Squares of Orders N>9 (in Russian) // Science and education in the development of industrial, social and economic spheres of Russian regions. Murom, 2022. pp. 314-315.
Eduard I. Vatutin, Best known examples.
Index entries for sequences related to Latin squares and rectangles.

Cf. A274806, A287644, A287645, A287647, A342997, A345370.

a(8) added by Eduard I. Vatutin, Oct 29 2017

a(9) added by Eduard I. Vatutin, Dec 08 2020

A287647 Minimum number of diagonal transversals in a diagonal Latin square of order n.

Original entry on oeis.org

1, 0, 0, 4, 1, 2, 0, 0, 0

Offset: 1

Eduard I. Vatutin, May 29 2017

A007016 is an upper bound for the number of diagonal transversals in a Latin square: a(n) <= A287648(n) <= A007016(n). - Eduard I. Vatutin, Jan 02 2020
From Eduard I. Vatutin, Apr 26 2021: (Start)
A diagonal Latin square is a Latin square in which both the main diagonal and main antidiagonal contain each element.
A diagonal transversal is a transversal that includes exactly one element from the main diagonal and exactly one from the antidiagonal. For squares of odd orders, these elements can coincide at the intersection of the diagonals.
All cyclic diagonal Latin squares (see A338562) are diagonal Latin squares, so a(n) <= A342998((n-1)/2). (End)
a(10) <= 3, a(11) <= 43, a(12) = 0, a(13) <= 4756, a(14) <= 1446, a(15) <= 15510, a(16) <= 898988, a(17) <= 12058840, a(18) <= 82577875, a(19) <= 592174879, a(20) <= 4488686380. - Eduard I. Vatutin, Sep 26 2021, updated Jan 20 2025

			From _Eduard I. Vatutin_, Apr 26 2021: (Start)
For example, the diagonal Latin square
  0 1 2 3
  3 2 1 0
  1 0 3 2
  2 3 0 1
has 4 diagonal transversals:
  0 . . .    . 1 . .    . . 2 .    . . . 3
  . . 1 .    . . . 0    3 . . .    . 2 . .
  . . . 2    . . 3 .    . 0 . .    1 . . .
  . 3 . .    2 . . .    . . . 1    . . 0 .
In addition there are 4 other transversals that are not diagonal transversals and are therefore not included here. (End)

E. I. Vatutin, Discussion about properties of diagonal Latin squares, forum.boinc.ru (in Russian)
E. I. Vatutin, About the minimal number of diagonal transversals in a diagonal Latin squares of order 9 (in Russian)
Eduard I. Vatutin, Best known examples.
E. I. Vatutin, S. E. Kochemazov and O. S. Zaikin, Estimating of combinatorial characteristics for diagonal Latin squares, Recognition — 2017 (2017), pp. 98-100 (in Russian)
E. I. Vatutin, S. E. Kochemazov, O. S. Zaikin and S. Yu. Valyaev, Enumerating the Transversals for Diagonal Latin Squares of Small Order. CEUR Workshop Proceedings. Proceedings of the Third International Conference BOINC-based High Performance Computing: Fundamental Research and Development (BOINC:FAST 2017). Vol. 1973. Technical University of Aachen, Germany, 2017. pp. 6-14. urn:nbn:de:0074-1973-0.
E. I. Vatutin, S. E. Kochemazov, O. S. Zaikin and S. Yu. Valyaev, Using Volunteer Computing to Study Some Features of Diagonal Latin Squares. Open Engineering. Vol. 7. Iss. 1. 2017. pp. 453-460. DOI: 10.1515/eng-2017-0052
E. I. Vatutin, S. E. Kochemazov, O. S. Zaikin, S. Yu. Valyaev and V. S. Titov, Estimating the Number of Transversals for Diagonal Latin Squares of Small Order, Telecommunications. 2018. No. 1. pp. 12-21 (in Russian).
Eduard I. Vatutin, Natalia N. Nikitina and Maxim O. Manzuk, First results of an experiment on studying the properties of DLS of order 9 in the volunteer distributed computing projects Gerasim@Home and RakeSearch (in Russian).
E. I. Vatutin, N. N. Nikitina, M. O. Manzuk, A. M. Albertyan, and I. I. Kurochkin, On the construction of spectra of fast-computable numerical characteristics for diagonal Latin squares of small order, Intellectual and Information Systems (Intellect - 2021). Tula, 2021. pp. 7-17. (in Russian)
E. I. Vatutin, N. N. Nikitina, M. O. Manzuk, I. I. Kurochkin, A. M. Albertyan, A. V. Kripachev, and A. I. Pykhtin, Methods for getting spectra of fast computable numerical characteristics of diagonal Latin squares, Cloud and distributed computing systems in electronic control conference, within the National supercomputing forum (NSCF - 2022). Pereslavl-Zalessky, 2023. pp. 19-23. (in Russian)
E. I. Vatutin, V. S. Titov, A. I. Pykhtin, A. V. Kripachev, N. N. Nikitina, M. O. Manzuk, A. M. Albertyan and I. I. Kurochkin, Estimation of the Cardinalities of the Spectra of Fast-computable Numerical Characteristics for Diagonal Latin Squares of Orders N>9 (in Russian) // Science and education in the development of industrial, social and economic spheres of Russian regions. Murom, 2022. pp. 314-315.
Index entries for sequences related to Latin squares and rectangles.

Cf. A287644, A287645, A287648, A342998, A345370.

a(8) added by Eduard I. Vatutin, Oct 29 2017

a(9) added by Eduard I. Vatutin, Sep 20 2020

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

A341585 Number of main classes of cyclic diagonal Latin squares of order 2n+1.

Original entry on oeis.org

1, 0, 1, 1, 0, 2, 3, 0, 4, 4, 0, 5, 1, 0, 7, 7, 0, 1, 9, 0, 10, 10, 0, 11, 1, 0, 13, 2, 0, 14, 15, 0, 3, 16, 0, 17, 18, 0, 4, 19, 0, 20, 4, 0, 22, 5, 0, 4, 24, 0, 25, 25, 0, 26, 27, 0, 28, 5, 0, 7, 2, 0, 1, 31, 0, 32, 8, 0, 34, 34, 0, 10, 7, 0, 37, 37, 0, 7, 39, 0, 10

Offset: 0

Eduard I. Vatutin, Feb 15 2021

nonn

There are no cyclic diagonal Latin squares of even order.
All cyclic diagonal Latin squares are pandiagonal. Conversely, all pandiagonal Latin squares are cyclic for orders 5, 7 and 11.
From Andrew Howroyd, May 01 2021: (Start)
Depending on exactly which Latin squares constitute a main class, slightly different sequences are possible. Another variation is given in A343866.
In this sequence equivalence allows for the permutation of symbols, the transpose of rows with columns, and any permutation of rows and columns that preserves the cyclic and diagonal properties. This permutation must transform every cyclic diagonal Latin square into another, but does not necessarily transform an arbitrary diagonal Latin square that is not cyclic into another diagonal Latin square.
The row (or column) permutations that satisfy this requirement form a group and are those where every k-th row (or column) is taken cyclically where k is any number that is congruent to 1 or -1 modulo every prime divisor of the order of the Latin square. (End)

			For n=0 there is only 1 Latin square of order 1, so a(0)=1.
For n=2 there is one main class with canonical form (CF) of cyclic diagonal Latin squares of order 2n+1=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
so a(2)=1.
For n=3 there is one main class of order 7 with CF:
  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
so a(3)=1.
a(12) = 1. There are A123565(25) = 10 cyclic diagonal Latin squares whose first row is in ascending order. The 10 row permutations constructed by selecting every k-th row cyclically where k is one of 1, 4, 6, 9, 11, 14, 16, 19, 21, 24 (numbers congruent to 1 or -1 modulo 5) transforms each of these between each other so there is only a single class. - _Andrew Howroyd_, May 02 2021

Eduard I. Vatutin, About the number of main classes of pandiagonal Latin squares of orders 1-12 and cyclic diagonal Latin squares of orders 1-22 (in Russian).
Eduard I. Vatutin, About the number of cyclic diagonal Latin squares of orders 23-24 (in Russian).
Eduard I. Vatutin, Enumerating the Main Classes of Cyclic and Pandiagonal Latin Squares, Recognition — 2021, pp. 77-79. (in Russian)
Eduard I. Vatutin, Proving list.
Index entries for sequences related to Latin squares and rectangles.

Cf. A123565, A338562, A343866.

G(n)={my(f=factor(n)[,1]); select((d->for(i=1, #f, if((d-1)%f[i]&&(d+1)%f[i], return(0)));1), [1..n])}
iscanon(n,k,g) = k <= vecmin(g*k%n) && k <= vecmin(g*lift(1/Mod(k,n))%n)
a(n)={if(n==0, 1, my(m=2*n+1, g=G(m)); sum(k=1, m-1, gcd(m,k)==1 && gcd(m,k-1)==1 && gcd(m,k+1)==1 && iscanon(m, k, g)))} \\ Andrew Howroyd, Apr 30 2021

a((p-1)/2) = A343866((p-1)/2) for odd prime p. - Andrew Howroyd, May 02 2021

Offset corrected and terms a(12) and beyond from Andrew Howroyd, Apr 30 2021

A342998 Minimum number of diagonal transversals in a cyclic diagonal Latin square of order 2n+1.

Original entry on oeis.org

1, 0, 5, 27, 0, 4523, 128818, 0, 204330233, 11232045257

Offset: 0

Eduard I. Vatutin, Apr 02 2021

A cyclic Latin square is a Latin square in which row i is obtained by cyclically shifting row i-1 by d places (see A338562, A123565 and A341585).
Cyclic diagonal Latin squares do not exist for even orders.
a(n) <= A342997(n).
All cyclic diagonal Latin squares are diagonal Latin squares, so A287647(n) <= a((n-1)/2).

			For n=2 one of best cyclic diagonal Latin squares 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
has a(2)=5 diagonal transversals:
  0 . . . .   . 1 . . .   . . 2 . .   . . . 3 .   . . . . 4
  . . 4 . .   . . . 0 .   . . . . 1   2 . . . .   . 3 . . .
  . . . . 3   4 . . . .   . 0 . . .   . . 1 . .   . . . 2 .
  . 2 . . .   . . 3 . .   . . . 4 .   . . . . 0   1 . . . .
  . . . 1 .   . . . . 2   3 . . . .   . 4 . . .   . . 0 . .

Eduard I. Vatutin, Enumerating the diagonal transversals for cyclic diagonal Latin squares of orders 1-19 (in Russian).
Eduard I. Vatutin, Proving list (best known examples).
Index entries for sequences related to Latin squares and rectangles.

Cf. A006717, A123565, A287647, A287648, A338562, A341585, A342997.

A342306 Number of pandiagonal Latin squares of order 2n+1.

Original entry on oeis.org

1, 0, 240, 20160, 0, 319334400, 77127879628800, 0

Offset: 0

Eduard I. Vatutin, Mar 08 2021

A pandiagonal Latin square is a Latin square in which the diagonal, antidiagonal and all broken diagonals and antidiagonals are transversals.
For orders 5, 7 and 11 all pandiagonal Latin squares are cyclic, so a(n) = A338562(n) for n < 6. For n=6 (order 13) this is not true (from Dabbaghian and Wu).
Pandiagonal Latin squares exist only for odd orders not divisible by 3. - Andrew Howroyd, May 26 2021

			Example of a cyclic pandiagonal 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 pandiagonal 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
Example of a cyclic pandiagonal Latin square of order 11:
   0  1  2  3  4  5  6  7  8  9 10
   2  3  4  5  6  7  8  9 10  0  1
   4  5  6  7  8  9 10  0  1  2  3
   6  7  8  9 10  0  1  2  3  4  5
   8  9 10  0  1  2  3  4  5  6  7
  10  0  1  2  3  4  5  6  7  8  9
   1  2  3  4  5  6  7  8  9 10  0
   3  4  5  6  7  8  9 10  0  1  2
   5  6  7  8  9 10  0  1  2  3  4
   7  8  9 10  0  1  2  3  4  5  6
   9 10  0  1  2  3  4  5  6  7  8
For order 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).

A.O.L. Atkin, L. Hay, and R. G. Larson, Enumeration and construction of pandiagonal Latin squares of prime order, Computers & Mathematics with Applications, Volume. 9, Iss. 2, 1983, pp. 267-292.
Vahid Dabbaghian and Tiankuang Wu, Constructing non-cyclic pandiagonal Latin squares of prime orders, Journal of Discrete Algorithms 30, 2015.

Cf. A338562, A338620.

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

Zero terms for even orders removed by Andrew Howroyd, May 26 2021

A342997 Maximum number of diagonal transversals in a cyclic diagonal Latin square of order 2n+1.

Original entry on oeis.org

1, 0, 5, 27, 0, 4665, 131106, 0, 204995269, 11254190082

Offset: 0

Eduard I. Vatutin, Apr 02 2021

A cyclic Latin square is a Latin square in which row i is obtained by cyclically shifting row i-1 by d places (see A338562, A123565 and A341585).
Cyclic diagonal Latin squares do not exist for even n.
All cyclic diagonal Latin squares are diagonal Latin squares, so a((n-1)/2) <= A287648(n).
All diagonal transversals are transversals, so a(n) <= A006717(n).
A342998 <= a(n).

			For n=2 one of the best cyclic diagonal Latin squares 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
has a(2)=5 diagonal transversals:
  0 . . . .   . 1 . . .   . . 2 . .   . . . 3 .   . . . . 4
  . . 4 . .   . . . 0 .   . . . . 1   2 . . . .   . 3 . . .
  . . . . 3   4 . . . .   . 0 . . .   . . 1 . .   . . . 2 .
  . 2 . . .   . . 3 . .   . . . 4 .   . . . . 0   1 . . . .
  . . . 1 .   . . . . 2   3 . . . .   . 4 . . .   . . 0 . .

Eduard I. Vatutin, Enumerating the diagonal transversals for cyclic diagonal Latin squares of orders 1-19 (in Russian).
Eduard I. Vatutin, Proving list (best known examples).
Index entries for sequences related to Latin squares and rectangles.

Cf. A006717, A123565, A287648, A338562, A341585, A342998.

A372922 Number of diagonal Latin squares of order 2n+1 that are isomorphic to cyclic Latin squares by row and column permutations.

Original entry on oeis.org

1, 0, 480, 161280, 2229534720, 45984153600000, 3271798279766016000

Offset: 0

Eduard I. Vatutin, May 16 2024

The Latin squares considered here are diagonal Latin squares that are isomorphic to cyclic Latin squares. They are can be obtained from cyclic Latin squares (see A338522) by diagonalization (getting a corresponding pair of transversals and placing them on the diagonals, see article). These Latin squares have some interesting properties, for example, there are a large number of diagonal transversals.

			The cyclic Latin square of order 7
.
  0 1 2 3 4 5 6
  1 2 3 4 5 6 0
  2 3 4 5 6 0 1
  3 4 5 6 0 1 2
  4 5 6 0 1 2 3
  5 6 0 1 2 3 4
  6 0 1 2 3 4 5
.
has a pair of symmetrically placed transversals T1 = (0, 2, 4, 6, 1, 3, 5) and T2 = (0, 5, 3, 1, 6, 4, 2), after permutting rown and columns transversal T1 placed to the main diagonal with getting single diagonal Latin square
.
  2 5 0 3 4 6 1
  0 3 5 1 2 4 6
  1 4 6 2 3 5 0
  6 2 4 0 1 3 5
  3 6 1 4 5 0 2
  4 0 2 5 6 1 3
  5 1 3 6 0 2 4
.
then after permuting rows and columns transversal T2 placed to the second diagonal with getting diagonal Latin square
.
  2 5 0 3 6 1 4
  0 3 5 1 4 6 2
  1 4 6 2 5 0 3
  6 2 4 0 3 5 1
  4 0 2 5 1 3 6
  5 1 3 6 2 4 0
  3 6 1 4 0 2 5
.
that can be canonized to the following diagonal Latin square:
.
  0 1 2 3 4 5 6
  2 3 1 5 6 4 0
  5 6 4 0 1 2 3
  4 0 6 2 3 1 5
  6 2 0 1 5 3 4
  1 5 3 4 0 6 2
  3 4 5 6 2 0 1
.
Cyclic Latin square of order 11
.
  0 1 2 3 4 5 6 7 8 9 10
  1 2 3 4 5 6 7 8 9 10 0
  2 3 4 5 6 7 8 9 10 0 1
  3 4 5 6 7 8 9 10 0 1 2
  4 5 6 7 8 9 10 0 1 2 3
  5 6 7 8 9 10 0 1 2 3 4
  6 7 8 9 10 0 1 2 3 4 5
  7 8 9 10 0 1 2 3 4 5 6
  8 9 10 0 1 2 3 4 5 6 7
  9 10 0 1 2 3 4 5 6 7 8
  10 0 1 2 3 4 5 6 7 8 9
.
can be diagonalized to set of diagonal Latin squares:
.
  0 1 2 3 4 5 6 7 8 9 10   0 1 2 3 4 5 6 7 8 9 10   0 1 2 3 4 5 6 7 8 9 10
  1 2 3 4 5 10 8 9 0 6 7   1 2 3 4 6 7 8 9 10 0 5   1 2 3 4 5 10 9 0 7 8 6
  3 4 5 10 7 9 1 8 2 0 6   8 10 5 7 9 3 0 4 1 6 2   3 4 5 10 6 9 7 2 1 0 8
  4 5 10 7 9 6 2 0 3 1 8   4 6 8 10 5 1 7 2 9 3 0   10 6 9 8 7 0 2 5 4 3 1
  10 7 9 6 8 0 4 2 5 3 1   9 0 1 2 3 10 4 5 6 7 8   9 8 7 0 1 2 4 6 10 5 3
  7 9 6 8 0 1 5 3 10 4 2   7 9 0 1 2 8 3 10 4 5 6   5 10 6 9 8 7 1 4 3 2 0
  8 0 1 2 3 4 9 10 6 7 5   6 8 10 5 7 2 9 3 0 4 1   7 0 1 2 3 4 10 8 9 6 5
  2 3 4 5 10 7 0 6 1 8 9   10 5 7 9 0 4 1 6 2 8 3   4 5 10 6 9 8 0 3 2 1 7
  5 10 7 9 6 8 3 1 4 2 0   3 4 6 8 10 0 5 1 7 2 9   8 7 0 1 2 3 5 9 6 10 4
  6 8 0 1 2 3 7 5 9 10 4   2 3 4 6 8 9 10 0 5 1 7   6 9 8 7 0 1 3 10 5 4 2
  9 6 8 0 1 2 10 4 7 5 3   5 7 9 0 1 6 2 8 3 10 4   2 3 4 5 10 6 8 1 0 7 9 ...
.
(totally 81 main classes of diagonal Latin squares).

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)
Eduard I. Vatutin, About the different types of cyclic diagonal Latin squares (in Russian).
E. Vatutin, A. Belyshev, N. Nikitina, M. Manzuk, A. Albertian, I. Kurochkin, A. Kripachev, and A. Pykhtin, Diagonalization and Canonization of Latin Squares, Lecture Notes in Computer Science, Vol. 14389, Springer, Cham., 2023. pp. 48-61.
Index entries for sequences related to Latin squares and rectangles.

Cf. A338522, A338562, A342990, A372923, A375475.

a(n) = A372923(n) * (2n+1)!. - Eduard I. Vatutin, Sep 08 2024

A348212 Number of transversals in a cyclic diagonal Latin square of order 2n+1.

Original entry on oeis.org

1, 0, 15, 133, 0, 37851, 1030367, 0, 1606008513, 87656896891, 0, 452794797220965, 41609568918940625

Offset: 1

Eduard I. Vatutin, Oct 07 2021

All cyclic diagonal Latin squares of order n have same number of transversals. A similar statement for diagonal transversals is not true (see A342998 and A342997).
All broken diagonals and antidiagonals of cyclic Latin squares are transversals, so a(n) >= 2*n for all n > 1 for which cyclic diagonal Latin squares exist. - Eduard I. Vatutin, Mar 22 2022
All cyclic diagonal Latin squares are diagonal Latin squares, so A287645(2n+1) <= a(n) <= A287644(2n+1) for all orders in which cyclic diagonal Latin squares exist. - Eduard I. Vatutin, Mar 23 2022

			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
has a(3)=15 transversals:
  0 . . . .   0 . . . .   . 1 . . .         . . . . 4
  . 3 . . .   . . . . 1   2 . . . .         . 3 . . .
  . . 1 . .   . . . 2 .   . . . . 3         . . . 2 .
  . . . 4 .   . . 3 . .   . . . 4 .         1 . . . .
  . . . . 2   . 4 . . .   . . 0 . .   ...   . . 0 . .

Eduard I. Vatutin, About the number of transversals in cyclic Latin and cyclic diagonal Latin squares (in Russian).
Index entries for sequences related to Latin squares and rectangles.

Cf. A006717, A011655, A287644, A287645, A338562, A342997, A342998.

a(n) = A006717(n) * A011655(n+1).

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

A287648 Maximum number of diagonal transversals in a diagonal Latin square of order n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A287647 Minimum number of diagonal transversals in a diagonal Latin square of order n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A341585 Number of main classes of cyclic diagonal Latin squares of order 2n+1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A342998 Minimum number of diagonal transversals in a cyclic diagonal Latin square of order 2n+1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A342306 Number of pandiagonal Latin squares of order 2n+1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A342997 Maximum number of diagonal transversals in a cyclic diagonal Latin square of order 2n+1.

Views

Author

Keywords

Comments

Examples