|
| |
|
|
A309500
|
|
The minimal number of steps to return to the origin for a self-avoiding walk with step-length n on 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.
|
|
3
|
|
|
|
4, 4, 4, 4, 36, 4, 4, 4, 4, 36, 4, 4, 122, 4, 36, 4, 198, 4, 4, 36, 4, 4, 4, 4, 436, 122, 4, 4, 632, 36, 4, 4, 4, 198, 36, 4, 694, 4, 122, 36
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
Consider a walk on a 2D plane starting at the (0,0) origin. We introduce the following rules for the walk: 1. Each step is of length n. 2. The walk can only step to points with integer x and y coordinates. 3. The walk cannot go to a 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, what is the minimum number of steps required for the walk to return to the origin? For step length n the sequence a(n) is the minimum number of steps.
For step lengths n which are not hypotenuses of any Pythagorean triple the solution is 4 as the walk will simply trace out a square e.g. step up, then right (or left), then down, then left (or right) back to the origin. This is true for n=1,2,3,4. But for step length 5 if the initially step is to (0,5) then by the rules the closest point to the origin for the next step now becomes (3,1) - the step must take the hypotenuse of a (3,4,5) triangle as clearly (3,1) is closer to the origin than (5,5). From here the walk must continue to pick the next point as close as possible to the origin which is 5 units away from its current coordinate, either directly left-right-up-down or by moving along the hypotenuse of a (3,4,5) triangle. Also note for n=5, and any step length which is the hypotenuse of a Pythagorean triple, the walk can also take a first step to (4,3) - this can result in a totally different path that may, or may not, lead back to the origin in fewer steps.
If the walk visits a point either on the x=0 or y=0 axis, or along the line y=x or y=-x, then it is likely that for the next step two points will be available which are equidistant from the origin. As we do not know which will lead to the minimum length walk we are searching for, the walker must explore both paths. Although the values of a(n) for the primitive Pythagorean triples are not particularly large, the total number of paths that must be recursively searched to find these minimum values increases extremely rapidly - to find a(37) required searching at least 400 million different paths, these being cut off by the walk either returning to the origin in fewer steps than the current minimum path, or by their step count surpassing the current minimum path. Due to the explosive increase in the total number of paths the exact value has only been determined for n=5. Assuming a first step to (0,5) or (4,3) the total number of paths is 26421. A n=5 random walk therefore has about a 1 in 2400 chance of taking one of the minimum 36 step walks.
For a(n) up to 40 it is found that for all n corresponding to Pythagorean triple hypotenuses that there are multiple paths corresponding to the minimum path value e.g. for n=5 there are 11 different paths all of which return to the origin after 36 steps. For n=37 there are 2048 different paths, once again showing the rapid increase in the total paths that must be explored to find the minimum.
Integer multiples of the hypotenuses of the primitive Pythagorean triples result in the same values for a(n) - simply scaling up the step length does not change the minimum path. However this is not necessarily true if the resulting hypotenuse has more than one triple e.g. n=25. The addition choice of a second Pythagorean triple greatly increases the number of paths to explore: finding a(26), which is the same as a(13), required searching about 550 paths, but a(25) requires searching at least 37 million paths.
It seems plausible that the path could be trapped by surrounding visited points during a very long walk and thus never be able to return to the origin. It is unknown if this can occur.
The author thanks Zachary Shannon and David Gundersen for discussions and efficiency improvements to the search program.
All terms are even. For odd n, consider the grid colored like a chessboard. It follows from the parity relation of Pythagorean triples that the destination of each step is of different color than the source. Hence each closed walk takes an even number of steps. For even n, no odd coordinates can be encountered, so we can divide the problem size by 2 until we are back in the odd case.
a(41) <= 1244 ; a(53) = 1528. (End)
a(61) <= 3698 ; a(73) = 3080 ; a(89) = 1034 ; a(97) = 4734. These results indicate that for hypotenuse lengths n which have legs of approximately the same length the number of search paths to find the minimum is relatively small. For lengths which have legs of uneven length, e.g. 41, the number of search paths becomes extremely large; n = 41 requires searching at least 10^12 paths. (End)
|
|
|
LINKS
|
Scott R. Shannon, Walk path for n=5. For this, and other images, the line colors are scaled from red to violet to show the relative step at which the point was visited. A white square marks the origin, a red square the first step point, and a violet square the last point before return to the origin, the path of which is marked with a white line. In this image only the smaller yellow squares indicate the points where the path had a choice of 2 points to go to which were equidistant from the origin. This is one of eleven different paths which return to the origin in 36 steps.
Scott R. Shannon, Visited points for n=5. These points show a pattern which is repeated in the other minimum step walks - the majority of points about half a step length away from the origin are visited. This eventually forces the walk to move away from the origin at which point a coordinate one step length away from the origin is finally visited.
Scott R. Shannon, Visited points for n=25. This clearly shows the tendency for the minimal path to cover the points half a step length away from the origin before visiting the last point which is one step length away from the origin.
Scott R. Shannon, Walk path for n=29. As the Pythagorean triple for 29 is (20,21,29) the diagonal steps are almost at 45 degrees to the axis which causes this path to form, in the authors opinion, a very aesthetically pleasing pattern. The next step length with legs one unit apart which has no other Pythagorean triples, and is thus likely to form a similar pattern, is 5741. Unfortunately the number of search paths to find the minimum in this instance would be astronomically large.
|
|
|
FORMULA
|
For step length n, also equal to the hypotenuse of one Pythagorean triple (a,b,n) where a>b, the first step of the walk can be either along the y axis or along the hypotenuse diagonal in the positive x-y direction (all other direction choices are equivalent by rotation/reflection). In the former case the first point will be (0,n), and thus the second point will be (b,n-a). From here a step directly left to (-(n-b),n-a) or diagonally down and left to (-(a-b),-(b-(n-a)) result in points equidistant from the origin - both are sqrt(3n^2-2bn-2an) from (0,0). So after only two steps two valid branches arise both of which must be explored. If instead the first step is along the hypotenuse to (a,b) then using simple algebra one can show that the next step will be to (-(n-a),b) if n>2b, else it will be to (a-b,-(a-b)) for n<2b. Note that in the former case the path (0,0)->(a,b)->(-(n-a),b) is rotationally symmetric to the path (0,0)->(0,n)->(b,n-a), so for step lengths n with n>2b only one of these options needs to be explored.
|
|
|
EXAMPLE
|
a(1) = 4. Path: (0,0)->(0,1)->(1,1)->(1,0)->(0,0).
a(5) = 36. Path: (0,0)->(4,3)->(1,-1)->(-3,2)->(0,-2)->(0,3)->(-3,-1)->(2,-1)->(-2,2)->(1,-2)->(1,3)->(-2,-1)->(2,2)->(-1,-2)->(-1,3)->(3,0)->(-2,0)->(2,3)->(-1,-1)->(3,2)->(3,-3)->(0,1)->(0,-4)->(-3,0)->(2,0)->(-2,3)->(-2,-2)->(2,1)->(-1,-3)->(-1,2)->(2,-2)->(-2,1)->(1,-3)->(1,2)->(4,-2)->(0,-5)->(0,0). Note this path is one of eleven with a total path length of 36. Five of those eleven paths step to (-3,2) on the third step while the other six step to (-2,3). The first step to the point (4,3) is required - a first step to (0,5) results in a minimum path length of 40.
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,walk,more
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
