A307171 Maximum number of partial loops in a diagonal Latin square of order n.

0, 0, 0, 12, 8, 21, 53, 112

Offset

1,4

Comments

A loop in a Latin square is a sequence of cells v1=L[i1,j1] -> v2=L[i1,j2] -> v1=L[i2,j2] -> ... -> v2=L[im,j1] -> v1=L[i1,j1] of length 2*m that consists of a pair of values {v1, v2}. A partial loop is a loop of length < 2*n.

Links

Table of n, a(n) for n=1..8.

E. I. Vatutin, Discussion about properties of diagonal Latin squares at forum.boinc.ru (in Russian).

E. I. Vatutin, About the minimum and maximum number of partial loops in a diagonal Latin squares of order 8 (in Russian).

Eduard Vatutin, Alexey Belyshev, Natalia Nikitina, and Maxim Manzuk, Evaluation of Efficiency of Using Simple Transformations When Searching for Orthogonal Diagonal Latin Squares of Order 10, High-Performance Computing Systems and Technologies in Sci. Res., Automation of Control and Production (HPCST 2020), Communications in Comp. and Inf. Sci. book series (CCIS, Vol. 1304) Springer (2020), 127-146.

Eduard I. Vatutin, Proving list (best known examples).

Index entries for sequences related to Latin squares and rectangles.

Example

For example, the square
  2 4 3 5 0 1
  1 0 4 3 2 5
  0 2 5 4 1 3
  5 3 0 1 4 2
  4 5 1 2 3 0
  3 1 2 0 5 4
has a loop
  2 4 . . . .
  . . . . . .
  . 2 . 4 . .
  . . . . . .
  4 . . 2 . .
  . . . . . .
consisting of the sequence of cells L[1,1]=2 -> L[1,2]=4 -> L[3,2]=2 -> L[3,4]=4 -> L[5,4]=2 -> L[5,1]=4 -> L[1,1]=2 with length 6 < 12.
The total number of loops for this square is 21, all of which are partial.

Crossrefs

Cf. A307167, A307170.

Sequence in context: A094332 A324976 A261402 * A040134 A258641 A206478

Adjacent sequences: A307168 A307169 A307170 * A307172 A307173 A307174

Keyword

nonn,more,hard

Author

Eduard I. Vatutin, Mar 27 2019

Extensions

a(8) added by Eduard I. Vatutin, Oct 06 2020

Status

approved