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

%I #22 Feb 13 2022 09:23:34

%S 7,9,12,13,15,16,18,18,19,21,22,22,24,24,25,26,27,27,28,28,30,31,31,

%T 31,32,33,33,34,35,35,36,36,37,37,37

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

%C 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.

%H Pontus von Brömssen, <a href="/A351041/a351041.svg">Examples of optimal trajectories in A351041 for 1 <= n <= 8</a>.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Racetrack_(game)">Racetrack</a>

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

%F a(n) <= A351042(n).

%F 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.

%F 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).

%e The following diagrams show examples of optimal trajectories for n = 1, 2, 3. The origin is marked with an asterisk.

%e .

%e a(1) = 7:

%e . 2 . 1 . .

%e 3 . * . 0 7

%e . 5 . 6 . .

%e (The car stands still on the fourth step.)

%e .

%e a(2) = 9:

%e . 3 . 2 . .

%e 4 . . . 1 .

%e . . * . 0 9

%e 5 . . . 8 .

%e . 6 . 7 . .

%e .

%e a(3) = 12:

%e . . . 4 3 . . . .

%e . 5 . . . . 2 . .

%e . . . . . . . . .

%e 6 . . . . . . 1 .

%e 7 . . . * . . 0 12

%e . . . . . . . . .

%e . 8 . . . . . 11 .

%e . . . 9 . 10 . . .

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

%K nonn,more

%O 1,1

%A _Pontus von Brömssen_, Jan 29 2022