OFFSET
0,4
COMMENTS
"Loop" means any continuous curve starting and ending at the same point.
"Touch" includes vertices and edges of grid cells.
Equivalent to the Traveling Salesman Problem with unit square neighborhoods and a corner square starting point in an n X n grid.
The problem simplifies to vertex to vertex moves as shown in the StackExchange link.
Ideal loops would be solely made up of (1,1) moves, all of which touch the maximum number of 3 new unit squares. This is impossible in all cases n >= 3 and the following less efficient moves are known to be required:
a(3)..a(oo) contain 2/1 moves.
a(3) contains a 1/1 move.
a(5) contains a 2/sqrt(2) move.
a(7) contains a 4/sqrt(5) move.
Where moves are denoted in the (number of new squares touched)/(unit length) format.
Optimal loops for n >= 2 touch but do not enter the outermost ring of squares, thus the inner vertex of each of the four corner squares are visited in all those cases.
The area enclosed by any loop made up of fully efficient moves equals n^2/2-4. In the case of shortest loops, n >= 6 and n = 4 have this property. - Tamás Fülöp, Dec 23 2025
LINKS
Zoe Allen, Touching as many grid squares as possible with path of given length, Math StackExchange, Feb 18 2025.
Tamás Fülöp, C++ program, GitHub repository, Oct 07 2025.
Tamás Fülöp, All loops with n = 3 - 10, Nov 04 2025.
Tamás Fülöp, Recursive examples for the upper bounds, Nov 22 2025.
Wikipedia, Chebyshev distance.
FORMULA
a(n) >= A383980(n) + 2, if n >= 4, with equality if n == 0 (mod 6).
a(n) <= 2*n + (n*(n-4) )/3, if n == 0 (mod 6).
a(n) <= 2*n+6 + (n*(n-4)-12)/3, if n == 1 (mod 6) and n >= 13.
a(n) <= 2*n+10 + (n*(n-4)-20)/3, if n == 2 (mod 6) and n >= 14.
a(n) <= 2*n+6 + (n*(n-4)-12)/3, if n == 3 (mod 6) and n >= 9.
a(n) <= 2*n+6 + (n*(n-4)-12)/3, if n == 4 (mod 6) and n >= 10.
a(n) <= 2*n+4 + (n*(n-4)-8 )/3, if n == 5 (mod 6) and n >= 11.
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. See the recursive examples link for drawings.
EXAMPLE
a(0)..a(2) = 0. Degenerate cases: Nothing touches all elements of an empty set. A single point may touch all 1 or 4 squares.
a(3), a(4) = 4, 8. Both are the shortest loops over the inner vertex of each of the four corner squares.
a(7) = 22 = length of 15 (0,1)s + length of 5 (1,1)s + length of 1 (1,2). A loop where all (0,1) and (1,1) moves are fully efficient is brute-forced impossible. The next best thing is to append a (1,2) move to one of the A383980(7) paths to form a loop.
See GitHub link/loops file for the lists of coordinate pairs, see the all loops link for drawings.
CROSSREFS
KEYWORD
nonn,more
AUTHOR
Tamás Fülöp, Oct 07 2025
STATUS
approved