A351041 Minimal number of steps for a Racetrack car (using Moore neighborhood) to go around a circle of radius n.

7, 9, 12, 13, 15, 16, 18, 18, 19, 21, 22, 22, 24, 24, 25, 26, 27, 27, 28, 28, 30, 31, 31, 31, 32, 33, 33, 34, 35, 35, 36, 36, 37, 37, 37

Offset: 1

Author

Pontus von Brömssen, Jan 29 2022

Keywords

• nonn
• more

Comments

The car moves according to the rules of the game of Racetrack, i.e., if P, Q, and R are three successive positions of the car, both coordinates of the second difference (acceleration vector) P - 2Q + R must be 1, 0, or -1. The car starts with zero velocity at a point (x,0) for some integer x >= n, and finishes when it passes, or lands on, the positive x-axis after a complete counterclockwise lap around the origin. The line segments between successive positions must be outside or on the circle with center in (0,0) and radius n.

Examples

			The following diagrams show examples of optimal trajectories for n = 1, 2, 3. The origin is marked with an asterisk.
.
  a(1) = 7:
  .  2  .  1  .  .
  3  .  *  .  0  7
  .  5  .  6  .  .
  (The car stands still on the fourth step.)
.
  a(2) = 9:
  .  3  .  2  .  .
  4  .  .  .  1  .
  .  .  *  .  0  9
  5  .  .  .  8  .
  .  6  .  7  .  .
.
  a(3) = 12:
  .  .  .  4  3  .  .  .  .
  .  5  .  .  .  .  2  .  .
  .  .  .  .  .  .  .  .  .
  6  .  .  .  .  .  .  1  .
  7  .  .  .  *  .  .  0 12
  .  .  .  .  .  .  .  .  .
  .  8  .  .  .  .  . 11  .
  .  .  .  9  . 10  .  .  .
		

Links

• Pontus von Brömssen, Examples of optimal trajectories in A351041 for 1 <= n <= 8.
• Wikipedia, Racetrack

Crossrefs

Cf. A000217, A002024, A027434, A351042, A351349, A351350.

Formula

a(n) = min {k >= 6; A351349(k)/A351350(k) >= n^2}.

a(n) <= A351042(n).

a(n) >= A027434(n) + A027434(2*n) + A002024(n). This can be seen by looking at the y-coordinate only: First, the car must go up to at least y = n and reduce the speed in the y-direction to zero in order to turn downwards; this requires at least A027434(n) steps. Then down to y = -n or below with speed reduced to zero; this requires at least A027434(2*n) steps. Finally, up to at least y = 0 (not necessarily reducing the speed); this requires at least A002024(n) steps.

It appears that a(n) = A027434(n) + A027434(2*n) + A002024(n) + 1 if n is a triangular number (A000217), otherwise a(n) = A027434(n) + A027434(2*n) + A002024(n).