

A374224


Integer part of the total Euclidean length of the shortest minimumlink polygonal chains joining all the nodes of the grid {0,1,...,n1} X {0,1,...,n1}.


0



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

This sequence describes the optimal solution of the 2D generalization of the wellknown nine dots problem, published in Loyd’s Cyclopedia of Puzzles (1914), p. 301.
Since Solomon Golomb constructively proved that, for any n >= 3, the minimumlink polygonal chain covering a given {0,1,...,n1} X {0,1,...,n1} 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,...,n1} X {0,1,...,n1} 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).


LINKS



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


EXAMPLE

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.


MATHEMATICA

Join[{0, 3, 12, 20, 28} Table[Floor[n^2 + 5*Sqrt[2]]  3 , {n, 6, 50}]]


CROSSREFS



KEYWORD

nonn,easy,new


AUTHOR



STATUS

approved



