This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A282425 #61 Aug 28 2017 03:14:23 %S A282425 0,5,16,45,84,163,260 %N A282425 The maximum number of steps Langton's ant can make confined to an n X n grid. %C A282425 a(8) >= 338, a(9) >= 397, a(10) >= 502. %C A282425 From _Rok Cestnik_, Aug 25 2017: (Start) %C A282425 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. %C A282425 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. %C A282425 Considered symmetries of the ant: %C A282425 1. rotational symmetry, e.g., we consider that the configuration %C A282425 +-----+-----+-----+ +-----+-----+-----+ %C A282425 | | |BBBBB| | | |BBBBB| | %C A282425 | v |BBBBB| | | |BBBBB| <-- | %C A282425 | |BBBBB| | | |BBBBB| | %C A282425 +-----+-----+-----+ +-----+-----+-----+ %C A282425 |BBBBB| | | is |BBBBB| |BBBBB| %C A282425 |BBBBB| | | equivalent |BBBBB| |BBBBB| %C A282425 |BBBBB| | | to |BBBBB| |BBBBB| %C A282425 +-----+-----+-----+ +-----+-----+-----+ %C A282425 | |BBBBB|BBBBB| |BBBBB| | | %C A282425 | |BBBBB|BBBBB| |BBBBB| | | %C A282425 | |BBBBB|BBBBB| |BBBBB| | | %C A282425 +-----+-----+-----+ +-----+-----+-----+ %C A282425 . %C A282425 2. mirror symmetry combined with color inversion, e.g., we consider that the configuration %C A282425 +-----+-----+-----+ +-----+-----+-----+ %C A282425 | |BBBBB| | |BBBBB| |BBBBB| %C A282425 | |BBBBB| <-- | |B-->B| |BBBBB| %C A282425 | |BBBBB| | |BBBBB| |BBBBB| %C A282425 +-----+-----+-----+ +-----+-----+-----+ %C A282425 |BBBBB| |BBBBB| is | |BBBBB| | %C A282425 |BBBBB| |BBBBB| equivalent | |BBBBB| | %C A282425 |BBBBB| |BBBBB| to | |BBBBB| | %C A282425 +-----+-----+-----+ +-----+-----+-----+ %C A282425 |BBBBB| | | |BBBBB|BBBBB| | %C A282425 |BBBBB| | | |BBBBB|BBBBB| | %C A282425 |BBBBB| | | |BBBBB|BBBBB| | %C A282425 +-----+-----+-----+ +-----+-----+-----+ %C A282425 . %C A282425 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 %C A282425 +-----+-----+-----+ +-----+-----+-----+ %C A282425 |BBBBB| |BBBBB| |BBBBB|BBBBB|BBBBB| %C A282425 |B-->B| |BBBBB| |BBBBB|BBBBB|BBBBB| %C A282425 |BBBBB| |BBBBB| |BBBBB|BBBBB|BBBBB| %C A282425 +-----+-----+-----+ +-----+-----+-----+ %C A282425 | |BBBBB| | will end |BBBBB|BBBBB|BBBBB| %C A282425 | |BBBBB| | in state |BBBBB|BBBBB|BBBBB| %C A282425 | |BBBBB| | |BBBBB|BBBBB|BBBBB| %C A282425 +-----+-----+-----+ +-----+-----+-----+ %C A282425 |BBBBB|BBBBB| | | | |BBBBB| %C A282425 |BBBBB|BBBBB| | | <-- | |BBBBB| %C A282425 |BBBBB|BBBBB| | | | |BBBBB| %C A282425 +-----+-----+-----+ +-----+-----+-----+ %C A282425 . %C A282425 and %C A282425 . %C A282425 +-----+-----+-----+ +-----+-----+-----+ %C A282425 |BBBBB|BBBBB|BBBBB| | | |BBBBB| %C A282425 |BBBBB|BBBBB|BBBBB| | ^ | |BBBBB| %C A282425 |BBBBB|BBBBB|BBBBB| | | | |BBBBB| %C A282425 +-----+-----+-----+ +-----+-----+-----+ %C A282425 |BBBBB|BBBBB|BBBBB| will end | |BBBBB| | %C A282425 |BBBBB|BBBBB|BBBBB| in state | |BBBBB| | %C A282425 |BBBBB|BBBBB|BBBBB| | |BBBBB| | %C A282425 +-----+-----+-----+ +-----+-----+-----+ %C A282425 |BBBBB| |BBBBB| |BBBBB|BBBBB| | %C A282425 |BB^BB| |BBBBB| |BBBBB|BBBBB| | %C A282425 |BB|BB| |BBBBB| |BBBBB|BBBBB| | %C A282425 +-----+-----+-----+ +-----+-----+-----+ %C A282425 . %C A282425 hence %C A282425 . %C A282425 +-----+-----+-----+ +-----+-----+-----+ %C A282425 |BBBBB| |BBBBB| |BBBBB|BBBBB|BBBBB| %C A282425 |B-->B| |BBBBB| |BBBBB|BBBBB|BBBBB| %C A282425 |BBBBB| |BBBBB| |BBBBB|BBBBB|BBBBB| %C A282425 +-----+-----+-----+ +-----+-----+-----+ %C A282425 | |BBBBB| | is |BBBBB|BBBBB|BBBBB| %C A282425 | |BBBBB| | equivalent |BBBBB|BBBBB|BBBBB| %C A282425 | |BBBBB| | to |BBBBB|BBBBB|BBBBB| %C A282425 +-----+-----+-----+ +-----+-----+-----+ %C A282425 |BBBBB|BBBBB| | |BBBBB| |BBBBB| %C A282425 |BBBBB|BBBBB| | |BB^BB| |BBBBB| %C A282425 |BBBBB|BBBBB| | |BB|BB| |BBBBB| %C A282425 +-----+-----+-----+ +-----+-----+-----+ %C A282425 (End) %C A282425 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. %H A282425 Rok Cestnik, <a href="/A282425/a282425.gif">Solution for n = 2</a> %H A282425 Rok Cestnik, <a href="/A282425/a282425_2.gif">Solution for n = 3</a> %H A282425 Rok Cestnik, <a href="/A282425/a282425_3.gif">Solution for n = 4</a> %H A282425 Rok Cestnik, <a href="/A282425/a282425_4.gif">Solution for n = 5</a> %H A282425 Rok Cestnik, <a href="/A282425/a282425_6.gif">Solution for n = 6</a> %H A282425 Rok Cestnik, <a href="/A282425/a282425_16.gif">Solution for n = 7</a> %H A282425 Rok Cestnik, <a href="/A282425/a282425.txt">C++ code for A282425</a> %H A282425 Rok Cestnik, <a href="/A282425/a282425_17.gif">Best found solution for n = 8</a> %H A282425 Rok Cestnik, <a href="/A282425/a282425_18.gif">Best found solution for n = 9</a> %H A282425 Rok Cestnik, <a href="/A282425/a282425_19.gif">Best found solution for n = 10</a> %H A282425 Wikipedia, <a href="https://en.wikipedia.org/wiki/Langton's_ant">Langton's ant</a> %Y A282425 Cf. A007764, A099733, A255938. %K A282425 nonn,hard,more %O A282425 1,2 %A A282425 _Rok Cestnik_, Feb 14 2017 %E A282425 a(7) from _Rok Cestnik_, Aug 12 2017