login
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.
2
8, 10, 16, 20, 22, 32, 40, 48
OFFSET
3,1
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
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.
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)
EXAMPLE
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.
CROSSREFS
KEYWORD
more,nonn
AUTHOR
Hagen von Eitzen, Sep 05 2009
STATUS
approved