A332939 The number of steps to return to the origin for a walk on a 2D square grid where the walk changes direction to move as close as possible toward the origin after it has taken a prime number of steps; backtracking on its previous step is not allowed.

0, 6, 18, 74, 110, 200, 268, 380, 574, 662, 828, 932, 1020, 1134, 1440, 1614, 1734, 1760, 1878, 1954, 2142, 2252, 2394, 2560, 2622, 2672, 2694, 2720, 2802, 2862, 3534, 3702, 3802, 3934, 4020, 4104, 4250, 4462, 4798, 5070, 5530, 5698, 5850, 5870, 5940, 6132, 6222, 6316, 6372

Offset: 0

Author

Scott R. Shannon, Mar 02 2020

Keywords

• nonn
• walk

Comments

Consider a walk on a 2D square grid which starts at the origin and may step in either the positive or negative x and y directions. The walk always continues in the direction of its last step until it has taken a number of steps equal to a prime number. The walk may then change to one of the four available directions so it subsequently moves as closely as possible toward the origin, the only restriction being it cannot choose the direction that will backtrack over its previous step. If the walks' location after a prime number of steps is exactly on one of the axes or on a 45-degree diagonal between the axes then it may choose either of the two equivalent directions as its next step, excluding backtracking.

Given these rules this sequence lists the number of steps the walk has taken when it returns to the origin. All terms are even due to the prime 3 being at relative coordinates (2,1) from the origin, and as all subsequent odd numbers are a multiple of two units away from 3 in the y direction an odd number can never have a zero y coordinate.

For a walk of 100 millions steps the walk returns to the origin 165960 times. The furthest distance from the origin is approximately 207.8 units, after step 20831533. The minimum steps between two origin visits is 6, which occurs at the beginning of the walk, from the first step to the sixth step. The maximum steps between origin visits is 7247, which occurs between steps 41331290 and 41338537.

Examples

			a(0) = 0 as the walk is at the origin after zero steps.
a(1) = 6 as from the origin the walk steps right until the number of steps it takes equals the first prime 2. After one more step upward the total steps equals the next prime 3. Two steps left reaches 5 steps, and then one step down back to the origin, taking 6 steps in all. The first step can be in either of the four symmetrically equivalent directions without changing the total steps back to the origin.
.
          5 -<- 4 -<- 3
          |           |
          \/          /\
          |           |
          * ->- 1 ->- 2   where * is the origin
.
a(2) = 18 as after the sixth step to the origin the walk continues down one more step reaching 7 steps, four steps right reaching 11 steps, two steps up to reach 13 steps, four steps left reaching 17 steps, then one step down back to the origin, giving 18 steps in all.
.
.        17 -<- 16 -<- 15 -<- 14 -<- 13
          |                          |
          \/                         /\
          |                          |
          *(6)                       12
          |                          |
          \/                         /\
          |                          |
          7 ->- 8 ->- 9  ->- 10 ->- 11   where * is the origin and previous step 6.
.
		

Links

• Scott R. Shannon, Image of the path traced out in the first 100 million steps. The step colors are graduated from red to violet to show the relative step order. The first and last step positions are shown as a white dot.

Crossrefs

Cf. A000040, A065358, A265843, A330339.