A351042 -id:A351042 - cp's OEIS frontend

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

Pontus von Brömssen, Jan 29 2022

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.

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

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

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

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

A351352 Denominator of the square of the radius of the largest circle, centered at the origin, around which a Racetrack car (using von Neumann neighborhood) can run a full lap in n steps.

Original entry on oeis.org

2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 5, 2, 2, 5, 13, 1, 13, 1, 25, 1, 1, 5, 1, 1

Offset: 8

Pontus von Brömssen, Feb 09 2022

The car starts and finishes on the positive x-axis, as in A351042.

The square of the radius of the largest circle is a rational number, because the squared distance from the origin to a line segment between two points with integer coordinates is always rational.

			See A351351 for examples.

Pontus von Brömssen, Some optimal Racetrack trajectories for A351351/A351352.
Wikipedia, Racetrack

Cf. A351042, A351350, A351351 (numerators).

A351043 Lexicographically earliest non-extendable Racetrack trajectory (using von Neumann neighborhood) on spiral on infinite square grid.

Original entry on oeis.org

0, 1, 9, 24, 46, 45, 21, 6, 4, 15, 33, 32, 12, 11, 10, 8, 7, 5, 16, 36, 63, 97, 96, 60, 13, 27, 50, 80, 119, 165, 164, 116, 75, 41, 68, 66, 64, 99, 141, 140, 138, 93, 55, 86, 84, 49, 79, 78, 76, 43, 69, 104, 102, 100, 143, 193, 192, 190, 137, 57, 54, 52, 25

Offset: 0

Pontus von Brömssen, Jan 30 2022

The car starts at square 0 and thereafter moves, according to the rules of Racetrack with von Neumann neighborhood (see A351042), to the lowest numbered unvisited square. The spiral numbering is described in A316328. After 146 steps, the car cannot move to any unvisited square, so the sequence is finite with 147 terms.

The position of the car after n steps is (A174344(a(n)+1), A274923(a(n)+1)). - Pontus von Brömssen, Jan 30 2025

Pontus von Brömssen, Table of n, a(n) for n = 0..146
Pontus von Brömssen, Trajectory of the Racetrack car in A351043.
Wikipedia, Racetrack

Cf. A174344, A274923, A316328, A351042.

A351351 Numerator of the square of the radius of the largest circle, centered at the origin, around which a Racetrack car (using von Neumann neighborhood) can run a full lap in n steps.

Original entry on oeis.org

1, 1, 2, 2, 4, 9, 9, 9, 16, 32, 32, 196, 81, 125, 392, 1225, 100, 1681, 160, 4489, 200, 225, 1369, 320, 400

Offset: 8

Pontus von Brömssen, Feb 09 2022

The car starts and finishes on the positive x-axis, as in A351042.

The square of the radius of the largest circle is a rational number, because the squared distance from the origin to a line segment between two points with integer coordinates is always rational.

			The following diagrams show examples of optimal trajectories for some values of n. The position of the car after k steps is labeled with the number k. If a number is missing, it means that the car stands still on that step. If the number 0 is missing (for the starting position), it means that the starting and finishing positions coincide. The origin is marked with an asterisk.
.
  n = 8 (r^2 = 1/2 = a(8)/A351352(8)):
  .  3  1
  4  *  8
  5  7  .
.
  n = 9 (r^2 = 1 = a(9)/A351352(9)):
  .  3  2  .  .
  4  .  .  1  .
  5  .  *  0  9
  .  6  7  8  .
.
  n = 10 (r^2 = 2 = a(10)/A351352(10)):
  .  .  3  2  .
  .  4  .  .  1
  5  .  *  . 10
  6  .  .  9  .
  .  7  8  .  .
.
  n = 12 (r^2 = 4 = a(12)/A351352(12)):
  .  4  3  2  .
  5  .  .  .  1
  6  .  *  . 12
  7  .  .  . 11
  .  8  9 10  .
.
  n = 13 (r^2 = 9 = a(13)/A351352(13)):
  .  .  .  4  .  3  .  .  .  .
  .  5  .  .  .  .  .  2  .  .
  6  .  .  .  .  .  .  .  1  .
  7  .  .  .  *  .  .  .  0 13
  8  .  .  .  .  .  .  .  .  .
  .  9  .  .  .  .  . 12  .  .
  .  .  . 10  . 11  .  .  .  .

Pontus von Brömssen, Some optimal Racetrack trajectories for A351351/A351352.
Wikipedia, Racetrack

Cf. A351042, A351349, A351350, A351352 (denominators).

a(n)/A351352(n) <= A351349(n)/A351350(n).

A380812 Sequence of x-coordinates of the lexicographically earliest (according to the spiral numbering of the square grid; see comments) infinite Racetrack trajectory (using von Neumann neighborhood) on the square grid.

Original entry on oeis.org

0, 1, 2, 2, 1, 0, -1, -1, -1, -1, 0, 1, 2, 2, 2, 1, 0, -1, -2, -3, -3, -2, -1, 0, 1, 3, 4, 4, 4, 3, 2, 1, -1, -3, -4, -4, -4, -4, -3, -2, 0, 2, 4, 5, 5, 4, 3, 2, 0, -2, -4, -5, -5, -5, -5, -4, -3, -1, 1, 3, 4, 4, 3, 2, 1, -1, -3, -5, -6, -6, -5, -3, 0, 3, 6, 8

Offset: 0

Pontus von Brömssen, Feb 05 2025

sign

The car starts at the origin and thereafter moves, according to the rules of Racetrack with von Neumann neighborhood (see A351042 or Wikipedia link), to the unvisited square that has the lowest spiral number, provided that it is possible to extend the trajectory to an infinite one. The spiral numbering is described in A316328.

The trajectory in A351043 is defined in a similar way, but it does not backtrack when it gets stuck, so it is finite, ending after 146 steps. The trajectory here is identical to the trajectory in A351043 for the first 144 steps.

			In the 144th step, the car moves from (-9,-8) to (-6,-6) (a(144) = A380813(144) = -6). A priori, the next possible positions (ordered by increasing spiral number) are (-3,-3), (-4,-4), (-3,-4), (-2,-4), and (-3,-5). Of these, (-3,-3) has already been visited (after the 103rd step), so the next choice is (-4,-4). From that position, however, the car is forced to move to (-2,-2) (all other alternatives have already been visited), and from (-2,-2) there are no available positions not already visited (so the trajectory in A351043 ends there). The next option (-3,-4) is also a dead end, but from (-2,-4) it is possible to continue forever, so a(145) = -2 and A380813(145) = -4.

Pontus von Brömssen, Table of n, a(n) for n = 0..10000
Pontus von Brömssen, Plot of the first 5000 steps of the trajectory.
Pontus von Brömssen, Plot of trajectory, using Plot2.
Wikipedia, Racetrack.

Cf. A174344, A316328, A351042, A351043, A380813 (y-coordinates), A380814.

a(n) = A174344(A351043(n)+1) for n <= 144.

A380813 Sequence of y-coordinates of the lexicographically earliest (according to the spiral numbering of the square grid; see comments) infinite Racetrack trajectory (using von Neumann neighborhood) on the square grid.

Original entry on oeis.org

0, 0, -1, -2, -3, -3, -2, -1, 1, 2, 3, 3, 2, 1, 0, -1, -1, 0, 2, 3, 4, 5, 5, 4, 2, 0, -2, -4, -5, -6, -6, -5, -4, -2, 0, 2, 4, 5, 6, 6, 6, 5, 3, 1, -1, -3, -4, -4, -4, -3, -1, 1, 3, 5, 6, 7, 7, 7, 6, 4, 2, 0, -2, -3, -4, -5, -5, -4, -3, -2, -1, 0, 1, 1, 0, -1

Offset: 0

Pontus von Brömssen, Feb 05 2025

sign

See A380812 for more details.
See A351042 or Wikipedia link for a description of the rules of Racetrack.
The trajectory in A351043 is defined in a similar way, but it does not backtrack when it gets stuck, so it is finite, ending after 146 steps. The trajectory here is identical to the trajectory in A351043 for the first 144 steps, and it turns out that the y-coordinates agree also for the last 2 steps.

Pontus von Brömssen, Table of n, a(n) for n = 0..10000
Pontus von Brömssen, Plot of the first 5000 steps of the trajectory.
Wikipedia, Racetrack.

Cf. A274923, A351042, A351043, A380812 (x-coordinates), A380814.

a(n) = A274923(A351043(n)+1) for n <= 146.

A351108 Triangle read by rows: T(m,n) is the number of simple paths for a Racetrack car (using von Neumann neighborhood) with initial velocity zero, going from one corner to the diagonally opposite corner on an m X n grid, 1 <= n <= m.

Original entry on oeis.org

1, 1, 0, 1, 1, 2, 2, 2, 3, 8, 3, 3, 7, 12, 40, 5, 7, 13, 26, 160, 1380, 9, 13, 28, 61, 918, 12940, 211164, 14, 27, 61, 161, 7260, 142453, 4997155, 205331148

Offset: 1

Pontus von Brömssen, Feb 01 2022

			Triangle begins:
  m\n|  1  2  3   4    5      6       7         8
  ---+-------------------------------------------
  1  |  1
  2  |  1  0
  3  |  1  1  2
  4  |  2  2  3   8
  5  |  3  3  7  12   40
  6  |  5  7 13  26  160   1380
  7  |  9 13 28  61  918  12940  211164
  8  | 14 27 61 161 7260 142453 4997155 205331148

Wikipedia, Racetrack

Cf. A064297, A291896 (column n=1), A351042, A351106, A351109 (main diagonal).

A351109 Number of simple paths for a Racetrack car (using von Neumann neighborhood) with initial velocity zero, going from one corner to the diagonally opposite corner on an n X n grid.

Original entry on oeis.org

1, 0, 2, 8, 40, 1380, 211164, 205331148

Offset: 1

Pontus von Brömssen, Feb 01 2022

			For n = 4 the following paths, together with their reflections in the diagonal, exist. The numbers give the positions of the car after successive steps. In total, there are a(4) = 2*4 = 8 possible paths.
  ...3  ...4  ...4  ...5
  ....  ...3  ..3.  ...4
  ..2.  ..2.  ..2.  ...3
  01..  01..  01..  012.

Wikipedia, Racetrack

Main diagonal of A351108.

Cf. A007764, A351042, A351107.

A351110 Triangle read by rows: T(m,n) is the number of paths for a Racetrack car (using Moore neighborhood) with initial velocity zero, going from one corner to the diagonally opposite corner on an m X n grid, such that all positions are visited exactly once, 1 <= n <= m.

Original entry on oeis.org

1, 1, 0, 1, 1, 6, 1, 0, 15, 2, 1, 1, 70, 289, 9436, 1, 0, 294, 191, 128020

Offset: 1

Pontus von Brömssen, Feb 01 2022

For a Racetrack car using von Neumann neighborhood (see A351042), there are no such paths if 2 <= n <= m, because the car will never be able to leave a corner of the grid (except the corner where it starts).

			Triangle begins:
  m\n| 1  2   3   4      5  6
  ---+-----------------------
  1  | 1
  2  | 1  0
  3  | 1  1   6
  4  | 1  0  15   2
  5  | 1  1  70 289   9436
  6  | 1  0 294 191 128020  ?

Wikipedia, Racetrack

Cf. A000012 (column n=1), A000035 (column n=2), A272445, A351041, A351042, A351106, A351111 (main diagonal).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A351352 Denominator of the square of the radius of the largest circle, centered at the origin, around which a Racetrack car (using von Neumann neighborhood) can run a full lap in n steps.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A351043 Lexicographically earliest non-extendable Racetrack trajectory (using von Neumann neighborhood) on spiral on infinite square grid.

Views

Author

Keywords

Comments

Links

Crossrefs

A351351 Numerator of the square of the radius of the largest circle, centered at the origin, around which a Racetrack car (using von Neumann neighborhood) can run a full lap in n steps.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A380812 Sequence of x-coordinates of the lexicographically earliest (according to the spiral numbering of the square grid; see comments) infinite Racetrack trajectory (using von Neumann neighborhood) on the square grid.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A380813 Sequence of y-coordinates of the lexicographically earliest (according to the spiral numbering of the square grid; see comments) infinite Racetrack trajectory (using von Neumann neighborhood) on the square grid.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A351108 Triangle read by rows: T(m,n) is the number of simple paths for a Racetrack car (using von Neumann neighborhood) with initial velocity zero, going from one corner to the diagonally opposite corner on an m X n grid, 1 <= n <= m.

Views

Author

Keywords

Examples

Links

Crossrefs

A351109 Number of simple paths for a Racetrack car (using von Neumann neighborhood) with initial velocity zero, going from one corner to the diagonally opposite corner on an n X n grid.

Views

Author

Keywords

Examples

Links

Crossrefs

A351110 Triangle read by rows: T(m,n) is the number of paths for a Racetrack car (using Moore neighborhood) with initial velocity zero, going from one corner to the diagonally opposite corner on an m X n grid, such that all positions are visited exactly once, 1 <= n <= m.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs