A282425 - OEIS

A282425

The maximum number of steps Langton's ant can make confined to an n X n grid.

0, 5, 16, 45, 84, 163, 260

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,2

COMMENTS

a(8) >= 338, a(9) >= 397, a(10) >= 502.

From Rok Cestnik, Aug 25 2017: (Start)

We are looking for the combination of grid configuration, ant orientation and ant position that yields the maximal number of steps before the ant leaves the grid. We consider all possible grid configurations and ant positions, but since the ant may move forward and backwards in time (see third considered symmetry below) we deduce that the maximal solution will always have the ant start from the edge of the grid.

For the sake of solution presentation, we consider these rules: at a white cell turn left, at a black cell turn right (vice versa results in the same behavior, just mirrored). Some cells might not get visited in a solution; therefore they are unconstrained, and we color then gray. We also take into consideration some symmetries of the ant to avoid presenting several maximal solutions that are just transformations of a single solution. That said, it is not impossible that two fundamentally different configurations would both have the same maximal number of steps.

Considered symmetries of the ant:

1. rotational symmetry, e.g., we consider that the configuration

+-----+-----+-----+ +-----+-----+-----+

| v |BBBBB| | | |BBBBB| <-- |

+-----+-----+-----+ +-----+-----+-----+

+-----+-----+-----+ +-----+-----+-----+

+-----+-----+-----+ +-----+-----+-----+

2. mirror symmetry combined with color inversion, e.g., we consider that the configuration

+-----+-----+-----+ +-----+-----+-----+

| |BBBBB| <-- | |B-->B| |BBBBB|

+-----+-----+-----+ +-----+-----+-----+

+-----+-----+-----+ +-----+-----+-----+

+-----+-----+-----+ +-----+-----+-----+

3. reversing the arrow of time combined with inverting the color of the cell on which the ant is located and turning the ant according to the color of its (now inverted) cell (with the chosen rules, if white turn left, if black turn right), e.g., the configuration

+-----+-----+-----+ +-----+-----+-----+

+-----+-----+-----+ +-----+-----+-----+

+-----+-----+-----+ +-----+-----+-----+

+-----+-----+-----+ +-----+-----+-----+

and

+-----+-----+-----+ +-----+-----+-----+

+-----+-----+-----+ +-----+-----+-----+

+-----+-----+-----+ +-----+-----+-----+

+-----+-----+-----+ +-----+-----+-----+

hence

+-----+-----+-----+ +-----+-----+-----+

+-----+-----+-----+ +-----+-----+-----+

+-----+-----+-----+ +-----+-----+-----+

+-----+-----+-----+ +-----+-----+-----+

(End)

Due to the ant's complex nature, its trajectory is hard to predict; therefore, an exhaustive search through the possible grid configurations must be performed, making this sequence computationally demanding.

LINKS

Table of n, a(n) for n=1..7.

Rok Cestnik, Solution for n = 2

Rok Cestnik, Solution for n = 3

Rok Cestnik, Solution for n = 4

Rok Cestnik, Solution for n = 5

Rok Cestnik, Solution for n = 6

Rok Cestnik, Solution for n = 7

Rok Cestnik, C++ code for A282425

Rok Cestnik, Best found solution for n = 8

Rok Cestnik, Best found solution for n = 9

Rok Cestnik, Best found solution for n = 10