cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-1 of 1 results.

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.

Original entry on oeis.org

8, 10, 16, 20, 22, 32, 40, 48
Offset: 3

Views

Author

Hagen von Eitzen, Sep 05 2009

Keywords

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

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)
Showing 1-1 of 1 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.