The OEIS is supported by the many generous donors to the OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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
 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 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). LINKS Table of n, a(n) for n=1..50. 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). 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 Cf. A002193, A010000, A058992, A373537. Sequence in context: A063244 A344015 A281813 * A063102 A122576 A212760 Adjacent sequences: A374221 A374222 A374223 * A374225 A374226 A374227 KEYWORD nonn,easy,new AUTHOR Marco Ripà, Jun 30 2024 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified August 4 13:44 EDT 2024. Contains 374923 sequences. (Running on oeis4.)