A165143 Length of longest cyclic knight path on an n X n chessboard that is determined (up to starting point and direction) by the fields visited.

8, 10, 16, 20, 22, 32, 40, 48

Offset: 3

Author

Hagen von Eitzen, Sep 05 2009

Keywords

• more
• nonn

Comments

More mathematically, a(n) is also the biggest possible number of vertices (or edges) of a circular graph in the plane with all vertices being distinct and having integer coordinates between 1 and n, inclusive, and all edges having length sqrt(5).

Opinions on a(1) and a(2) may differ: The only possible circular path consists of staying at the starting field, hence we have 1 field visited (thus a(1) = a(2) = 1) or it takes 0 knight moves to complete the tour (thus a(1) = a(2) = 0). The graph with one vertex and no edges is not considered a cyclic graph since all vertices must have degree two; even adding a loop edge would produce an edge of length 0 (thus a(1) and a(2) are either undefined or = 0 if one accepts the empty graph as cyclic).

Put another way, a(n) is the length of a longest induced cycle in the n X n knight graph. - Pontus von Brömssen, Oct 02 2022

Examples

			The eight non-center fields of a 3 X 3 chessboard can be visited cyclically in a unique manner up to selection of starting point and clockwise vs. counterclockwise direction; since the center field cannot be part of a (longer) cycle, we have a(3) = 8.
		

References

• Thomas Dawson, Échecs Féeriques, L'Échiquier, volume 2, issue 2, 1930; issue 3, 1931.
• Donald E. Knuth, The Art of Computer Programming, Volume 4B, Combinatorial Algorithms, Part 2, Addison-Wesley, 2023. See exercise 7.2.2.1-172 and its solution.

Links

• Nikolai Beluhov, Snake paths in king and knight graphs, arXiv:2301.01152 [math.CO], 2023.
• Sequence mentioned in the related Solution to problem #12, Missoury State Math Dept. Challenge Problem Archive, 2007/08.

Crossrefs

Cf. A297666, A357357, A357500, A357501.

Formula

From Pontus von Brömssen, Jan 30 2023: (Start)

a(n) = n^2/2 + O(n) (Beluhov 2023).

a(n) <= A357500(n)+1.

(End)