|
| |
|
|
A309501
|
|
a(n) is the minimal number of steps to return to the origin for a self-avoiding walk with step-length n 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.
|
|
1
|
|
|
|
4, 4, 4, 4, 20, 4, 4, 4, 4, 20, 4, 4, 6, 4, 20, 4, 120, 4, 4, 20, 4, 4, 4, 4, 6, 6, 4, 4, 32, 20, 4, 4, 4, 120, 20, 4, 6, 4, 6, 20, 6, 4, 4, 4, 20, 4, 4, 4, 4, 6, 120, 6, 2452, 4, 20, 4, 4, 32, 4, 20, 6, 4, 4, 4, 62, 4, 4, 120, 4, 20, 4, 4, 222, 6, 6
(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 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. Each step is of length n. 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, 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 required 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, then down, then left 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 while remaining inside the positive x-y quadrant. This can be achieved by stepping 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 along the line 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 rapidly. For example to find a(193) required searching at least 230,000 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.
For many n which are Pythagorean triple hypotenuses it is found that there are multiple paths corresponding to the minimum path value e.g. for n=29 there are 2 different paths which return to the origin after 32 steps. For n=73 there are 64 different paths.
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. for n=25 the step (7,24) is available as well as the primitive multiple (15,20). The former allows the walk to return to the origin in just 6 steps as opposed to 20 steps for a walk with step length of 5.
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.
For step length n equal to the hypotenuse of a Pythagorean triple (a,b,n) where 2b<a<n, a walk of only 6 steps back to the origin is available via the path (0,0)->(a,b)->(0,2b)->(n,2b)->(n-a,b)->(n,0)->(0,0). However for n values with multiple Pythagorean triples the above path may be broken if another point closer to the origin is available via a step from an alternative triple.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
a(1) = 4. Path: (0,0)->(0,1)->(1,1)->(1,0)->(0,0).
a(5) = 20. Path: (0,0)->(0,5)->(3,1)->(3,6)->(0,2)->(5,2)->(1,5)->(1,0)->(4,4)->(0,1)->(5,1)->(1,4)->(4,0)->(0,3)->(5,3)->(1,6)->(1,1)->(6,1)->(2,4)->(5,0)->(0,0).
a(13) = 6. Path: (0,0)->(12,5)->(0,10)->(13,10)->(1,5)->(13,0)->(0,0).
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,walk
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
