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

A287695 Maximum number of diagonal Latin squares with the first row in ascending order that can be orthogonal to a given diagonal Latin square of order n.

Original entry on oeis.org

1, 0, 0, 1, 1, 0, 3, 824, 614

Offset: 1

Eduard I. Vatutin, May 30 2017

A Latin square is normalized if in the first row elements come in increasing order. Any diagonal Latin square orthogonal to a given one can be normalized by renaming its elements (which does not break diagonality and orthogonality). - Max Alekseyev, Dec 07 2019
For all orders n>3 there are diagonal Latin squares without orthogonal mates (also known as bachelor squares), so the minimum number of diagonal Latin squares that can be orthogonal to the same diagonal Latin square is zero. For order n=1 the single square is orthogonal to itself. For n=2 and n=3 diagonal Latin squares do not exist (see A274171). For n=6 orthogonal diagonal Latin squares do not exist (see A305571), so a(6)=0. - Eduard I. Vatutin, May 03 2021
a(n) >= A328873(n) - 1. - Eduard I. Vatutin, Mar 29 2021
a(10) >= 10 (Updated). - Eduard I. Vatutin, Apr 27 2018
a(11) >= 32462. - Eduard I. Vatutin from T. Brada, Mar 11 2021
a(12) >= 3855983322. The result belongs to DLS, which has 30192 diagonal transversals. Calculations performed by a volunteer. - Natalia Makarova, Tomáš Brada, Nov 11 2021
a(13) >= 248703. - Natalia Makarova, Tomáš Brada, Apr 29 2021
a(14) >= 307662. - Natalia Makarova, Alex Chernov, Harry White, May 21 2021
a(16) >= 1658880, a(17) >= 2453352, a(18) >= 96, a(19) >= 1383, a(20) >= 995328, a(21) >= 995328, a(22) >= 432000, a(23) >= 525, a(24) >= 345600, a(25) >= 345600, a(26) >= 48, a(27) >= 345600, a(28) >= 663552, a(29) >= 663552, a(30) >= 40320. For values up to a(100), see the specified link "New boundaries for maximum number of normalized orthogonal diagonal Latin squares to one diagonal Latin square". - Natalia Makarova, Alex Chernov, Harry White, Dec 06 2021

			From _Eduard I. Vatutin_, Mar 29 2021: (Start)
One of the best existing diagonal Latin squares of order 7
  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
has 3 orthogonal mates
  0 1 2 3 4 5 6   0 1 2 3 4 5 6   0 1 2 3 4 5 6
  5 6 4 0 1 2 3   3 4 5 6 2 0 1   6 2 0 1 5 3 4
  1 5 3 4 0 6 2   4 0 6 2 3 1 5   3 4 5 6 2 0 1
  6 2 0 1 5 3 4   2 3 1 5 6 4 0   1 5 3 4 0 6 2
  3 4 5 6 2 0 1   5 6 4 0 1 2 3   2 3 1 5 6 4 0
  2 3 1 5 6 4 0   6 2 0 1 5 3 4   4 0 6 2 3 1 5
  4 0 6 2 3 1 5   1 5 3 4 0 6 2   5 6 4 0 1 2 3
so a(7)=3. (End)

Natalia Makarova, Diagonal Latin square with 10 orthogonal squares
Natalia Makarova, DB CF ODLS of order 9
Natalia Makarova, Maximum number of normalized ODLS from one DLS
Natalia Makarova, Comments for result a(12) >= 3855983322
Natalia Makarova, New boundaries for maximum number of normalized orthogonal diagonal Latin squares to one diagonal Latin square
Eduard I. Vatutin, Discussion about properties of diagonal Latin squares at forum.boinc.ru (in Russian).
Eduard I. Vatutin, Discussion about properties of diagonal Latin squares at forum.boinc.ru, square of order 9 with 516 orthogonal squares (in Russian).
Eduard I. Vatutin, About the A328873(N)-1 <= A287695(N) inequality between the maximum cardinality of clique and the maximum number of orthogonal normalized mates for one diagonal Latin square (in Russian).
Eduard I. Vatutin, About the diagonal Latin square of order 12 with 1764493860 orthogonal diagonal mates (in Russian).
Eduard I. Vatutin, Duplicate solutions removing using parallel and distributed DLX (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 (best known examples).
Eduard I. Vatutin, Stepan E. Kochemazov, Oleq 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.
Eduard I. Vatutin, S. E. Kochemazov, O. S. Zaikin, M. O. Manzuk and V. S. Titov, Combinatorial characteristics estimating for pairs of orthogonal diagonal Latin squares, Multicore processors, parallel programming, FPGA, signal processing systems (2017), pp. 104-111 (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, 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. A001438, A274171, A305571, A328873.

Definition corrected by Max Alekseyev, Dec 07 2019
a(9) added by Eduard I. Vatutin, Dec 12 2020
Edited by Max Alekseyev, Apr 01 2022

A001438 Maximal number of mutually orthogonal Latin squares (or MOLS) of order n.

Original entry on oeis.org

1, 2, 3, 4, 1, 6, 7, 8

Offset: 2

N. J. A. Sloane

By convention, a(0) = a(1) = infinity.
Parker and others conjecture that a(10) = 2.
It is also known that a(11) = 10, a(12) >= 5.
It is known that a(n) >= 2 for all n > 6, disproving a conjecture by Euler that a(4k+2) = 1 for all k. - Jeppe Stig Nielsen, May 13 2020

CRC Handbook of Combinatorial Designs, 1996, pp. 113ff.
S. Hedayat, N. J. A. Sloane and J. Stufken, Orthogonal Arrays, Springer-Verlag, NY, 1999, Chapter 8.
E. T. Parker, Attempts for orthogonal latin 10-squares, Abstracts Amer. Math. Soc., Vol. 12 1991 #91T-05-27.
David Wells, The Penguin Dictionary of Curious and Interesting Numbers, Penguin Books, 1997, p. 58.

Anonymous, Order-10 Greco-Latin square.
Thomas Bloom, Problem 724, Erdős Problems.
R. C. Bose and S. S. Shrikhande, On The Falsity Of Euler's Conjecture About The Non-Existence Of Two Orthogonal Latin Squares Of Order 4t+2, Proc. Nat. Acad. Sci., 1959 45 (5) 734-737.
R. Bose, S. Shrikhande, and E. Parker, Further Results on the Construction of Mutually Orthogonal Latin Squares and the Falsity of Euler's Conjecture, Canadian Journal of Mathematics, 12 (1960), 189-203.
C. J. Colbourn and J. H. Dinitz, Mutually Orthogonal Latin Squares: A Brief Survey of Constructions, preprint, Journal of Statistical Planning and Inference, Volume 95, Issues 1-2, 1 May 2001, Pages 9-48.
M. Dettinger, Euler's Square
David Joyner and Jon-Lark Kim, Kittens, Mathematical Blackjack, and Combinatorial Codes, Chapter 3 in Selected Unsolved Problems in Coding Theory, Applied and Numerical Harmonic Analysis, Springer, 2011, pp. 47-70, DOI: 10.1007/978-0-8176-8256-9_3.
Numberphile, Euler squares, YouTube video, 2020.
E. T. Parker, Orthogonal Latin Squares, Proc. Nat. Acad. Sci., 1959 45 (6) 859-862.
E. Parker-Woodruff, Greco-Latin Squares Problem
Tony Phillips, Mutually Orthogonal Latin Squares (MOLS), Latin Squares in Practice and in Theory II.
N. Rao, Shrikhande, "Euler's Spoiler", Turns 100, Bhāvanā, The mathematics magazine, Volume 1, Issue 4, 2017.
Eric Weisstein's World of Mathematics, Euler's Graeco-Roman Squares Conjecture
Wikipedia, Graeco-Latin square.
Index entries for sequences related to Latin squares and rectangles

Cf. A287695, A328873.

a(n) <= n-1 for all n>1. - Tom Edgar, Apr 27 2015
a(p^k) = p^k-1 for all primes p and k>0. - Tom Edgar, Apr 27 2015
a(n) = A107431(n,n) - 2. - Floris P. van Doorn, Sep 10 2019

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

A287695 Maximum number of diagonal Latin squares with the first row in ascending order that can be orthogonal to a given diagonal Latin square of order n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A001438 Maximal number of mutually orthogonal Latin squares (or MOLS) of order n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula