A374224 Integer part of the total Euclidean length of the shortest minimum-link polygonal chains joining all the nodes of the grid {0,1,...,n-1} X {0,1,...,n-1}.

0, 3, 12, 20, 28, 40, 53, 68, 85, 104, 125, 148, 173, 200, 229, 260, 293, 328, 365, 404, 445, 488, 533, 580, 629, 680, 733, 788, 845, 904, 965, 1028, 1093, 1160, 1229, 1300, 1373, 1448, 1525, 1604, 1685, 1768, 1853, 1940, 2029, 2120, 2213, 2308, 2405, 2504

Offset: 1

Author

Marco Ripà, Jun 30 2024

Keywords

• nonn
• easy

Comments

This sequence describes the optimal solution of the 2D generalization of the well-known nine dots problem, published in Loyd’s Cyclopedia of Puzzles (1914), p. 301.

Since Solomon Golomb constructively proved that, for any n >= 3, the minimum-link polygonal chain covering a given {0,1,...,n-1} X {0,1,...,n-1} grid consists of (exactly) 2*(n - 1) line segments, we only need to find the shortest trail satisfying the constraint above.

In detail, if n = 2, the trivial spanning path (0,1)-(0,0)-(1,0)-(1,1) is optimal. If n = 3, we have the classic solution of the nine dots problem (0,1)-(0,3)-(3,0)-(0,0)-(2,2). Now, if n > 3, a valid upper bound is given by n^2 + 5*sqrt(2) - 3, but it is possible to improve this solution for the n = 5 case by providing the trail.

(2,3)-(4,3)-(1,0)-(1,3)-(4,0)-(0,0)-(0,4)-(4,4)-(4,1), whose total Euclidean length is 20 + 6*sqrt(2). In the end, assuming n > 5, we can recycle the mentioned solution, then extend the last line segment to reach (4,-1), and finally apply the square spiral pattern to the (extended) ending segment of the {0,1,...,n-1} X {0,1,...,n-1} grid solution in order to get the solution for the {0,1,...,n} X {0,1,...,n} case, joining 2*n + 1 more points by spending two additional line segments having a combined length of 2*n (and this is an iterative strategy which is optimal for any n > 5).

Examples

			a(2) = 3 since we can join the points {0,1}^2 with a spanning path consisting of 3 line segments having a total Euclidean length of 2^2 - 1.
		

Links

• Marco Ripà, Shortest polygonal chains covering each planar square grid, arXiv:2207.08708 [math.CO], 2022. See pp. 11-13.
• Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

Crossrefs

Cf. A002193, A010000, A058992, A373537.

Programs

Mathematica

Join[{0, 3, 12, 20, 28} Table[Floor[n^2 + 5*Sqrt[2]] - 3 , {n, 6, 50}]]
LinearRecurrence[{3,-3,1},{0,3,12,20,28,40,53,68},50] (* Harvey P. Dale, Jul 19 2025 *)

Formula

a(1) = 1, a(2) = 3, a(3) = floor(5*(1+sqrt(2))) = 12, a(5) = floor(20 + 6*sqrt(2)) = 28, and a(n) = floor(n^2 + 5*sqrt(2)) - 3 iff n = 4 or n >= 6.

For n > 5, a(n) = n^2 + 4.

G.f.: x^2*(3 + 3*x - 7*x^2 + x^3 + 4*x^4 - 3*x^5 + x^6)/(1 - x)^3. - Stefano Spezia, Jul 02 2024