A307448 List of pairs of coordinates (x,y) of the visited points for a self-avoiding walk with an incrementing step length confined to one quadrant of a 2D plane where at each step the walk must go to an unvisited point with integer coordinates as close as possible to the origin.

0, 0, 0, 1, 2, 1, 2, 4, 2, 0, 2, 5, 8, 5, 1, 5, 9, 5, 0, 5, 10, 5, 10, 16, 10, 4, 5, 16, 5, 2, 5, 17, 5, 1, 5, 18, 5, 0, 5, 19, 17, 3, 17, 24, 17, 2, 17, 25, 17, 1, 2, 21, 26, 11, 26, 38, 26, 10, 5, 30, 23, 6, 23, 37, 23, 5, 23, 38, 7, 8, 42, 8, 6, 8, 43, 8, 5, 8, 44, 8, 4, 8, 45, 8, 3, 8, 46, 8, 2, 8, 47

Offset: 1

Author

Scott R. Shannon, Aug 09 2019

Keywords

• nonn
• walk
• tabf
• fini
• hear

Comments

Consider a walk on a 2D plane starting at the (0,0) origin which is confined to the positive x and y quadrant, i.e., x >= 0, y >= 0. We introduce the following rules for the walk: 1. The step length, initially 1, increments by 1 after each step. 2. The walk can only step to grid points with integer x and y coordinates. 3. The walk cannot go to a grid point already visited, nor can it backtrack on its very first step from the origin. 4. At each step the walk must always go to a point which is as close as possible to the origin. Given these rules, and a first step of length 1 to (0,1), this sequence gives the (x,y) coordinate points that are visited by the walk.

The sequence has 33305 pairs of coordinates. On the 33304th step the walk visits point (498,498) and now two points, (33803,498) and (498,33803), are both unvisited and available for the next step, thus beyond this point the walk/sequence is not uniquely defined.

For step lengths > 100 the closest approach to the origin is at step 2032 which visits point (6,0). The smallest ratio of distance-to-origin to step length occurs at step 27628 which visits point (7,15). The largest visited x and y coordinates are 42165 and 38631 respectively.

One finds there are long lines of adjacent visited points, differing by two step lengths, which are due to the path moving outward and then back inward along the x and y axial directions. These continue until the innermost point encounters an axis or a Pythagorean diagonal step is found which is closer to the origin. These adjacent points are equivalent to the points forming the 'concentric circles' of the Recamán sequence A005132 when plotted as a spiral. There is also a general clustering of the points towards the axis as well as the y=x diagonal.

This sequence raises the question - is there a walk that ultimately returns to the origin? Currently this is unknown. Beyond the 33304th point a recursive search must be perform on each branching path. Investigating beyond the first branching point show that the next branch occurs at step 200477, at point (121959,121959), followed by a series of branches at step lengths 472952, 730405, 974413.

Examples

			The first 12 steps are along the x-y axial directions. But on the 13th step the point (5,16) is available and the closest possible to the origin - this is visited by stepping along the hypotenuse of a (5,12,13) Pythagorean triangle from the point (10,4).
		

Links

• Scott R. Shannon, Table of n, a(n) for n = 1..66610
• Scott R. Shannon, Plot of points with x and y values less than 5000. In this and other images the pixel colors are scaled from red to violet to show the relative step at which the point was visited. Each pixel is one point. The final (498,498) point is plotted with a larger white square for clarity.
• Scott R. Shannon, Plot of all the sequence points. Due to the maximum x and y visited coordinate being much larger than the image size each pixel covers multiple points. For clarity each visited point is shown with a multi-pixel square.
• Scott R. Shannon, Plot of the walk steps. A small red dot near the origin is the final (498,498) point.
• Scott R. Shannon, Step visit to points for x<100 and y<100. This shows the step number at which each point was visited for points with x and y < 100. Best viewed using a text editor with word-wrapping turned off. The origin is marked as -1.
• Wikipedia, Pythagorean Triples.

Crossrefs

Cf. A020882, A009000, A005132.