A383980 Length of shortest path (in Chebyshev distance) that touches all cells in an n X n grid.

0, 0, 0, 3, 6, 10, 14, 20, 25, 31, 39

Offset

0,4

Comments

"Path" means any continuous curve between two points.

"Touch" includes vertices and edges of grid cells.

Links

Table of n, a(n) for n=0..10.

Zoe Allen, Touching as many grid squares as possible with path of given length, Math StackExchange, Feb 18 2025.

Tamás Fülöp, Minimal path to touch every square's area in an n by n grid, Math StackExchange, Feb 18 2025.

Tamás Fülöp, C++ program, GitHub repository, Apr 3 2025.

Tamás Fülöp, All paths with n = 3 - 10, Apr 23 2025.

Wikipedia, Chebyshev distance.

Formula

a(n) <= 2*n-2 + (n*(n-4) )/3, if n == 0 (mod 3) and n >= 6.

a(n) <= 2*n-2+3 + (n*(n-4)-6)/3, if n == 1 (mod 3) and n >= 7.

a(n) <= 2*n-2+1 + (n*(n-4)-2)/3, if n == 2 (mod 3) and n >= 5.

The linear term is the number of orthogonal moves, the quadratic term is the number of diagonal moves. These upper bounds match the shortest known lengths exactly.

a(n) <= A389534(n) - 2, if n >= 4, with equality if n == 0 (mod 6). - Tamás Fülöp, Dec 23 2025

Crossrefs

Cf. A389534.

Sequence in context: A330257 A079552 A334454 * A236758 A272058 A244360

Adjacent sequences: A383977 A383978 A383979 * A383981 A383982 A383983

Keyword

nonn,more,walk

Author

Tamás Fülöp, May 16 2025

Status

approved