A099733 -id:A099733 - cp's OEIS frontend

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

Offset: 1

Rok Cestnik, Feb 14 2017

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
    +-----+-----+-----+              +-----+-----+-----+
    |  |  |BBBBB|     |              |     |BBBBB|     |
    |  v  |BBBBB|     |              |     |BBBBB| <-- |
    |     |BBBBB|     |              |     |BBBBB|     |
    +-----+-----+-----+              +-----+-----+-----+
    |BBBBB|     |     |      is      |BBBBB|     |BBBBB|
    |BBBBB|     |     |  equivalent  |BBBBB|     |BBBBB|
    |BBBBB|     |     |      to      |BBBBB|     |BBBBB|
    +-----+-----+-----+              +-----+-----+-----+
    |     |BBBBB|BBBBB|              |BBBBB|     |     |
    |     |BBBBB|BBBBB|              |BBBBB|     |     |
    |     |BBBBB|BBBBB|              |BBBBB|     |     |
    +-----+-----+-----+              +-----+-----+-----+
.
  2. mirror symmetry combined with color inversion, e.g., we consider that the configuration
    +-----+-----+-----+              +-----+-----+-----+
    |     |BBBBB|     |              |BBBBB|     |BBBBB|
    |     |BBBBB| <-- |              |B-->B|     |BBBBB|
    |     |BBBBB|     |              |BBBBB|     |BBBBB|
    +-----+-----+-----+              +-----+-----+-----+
    |BBBBB|     |BBBBB|      is      |     |BBBBB|     |
    |BBBBB|     |BBBBB|  equivalent  |     |BBBBB|     |
    |BBBBB|     |BBBBB|      to      |     |BBBBB|     |
    +-----+-----+-----+              +-----+-----+-----+
    |BBBBB|     |     |              |BBBBB|BBBBB|     |
    |BBBBB|     |     |              |BBBBB|BBBBB|     |
    |BBBBB|     |     |              |BBBBB|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
    +-----+-----+-----+              +-----+-----+-----+
    |BBBBB|     |BBBBB|              |BBBBB|BBBBB|BBBBB|
    |B-->B|     |BBBBB|              |BBBBB|BBBBB|BBBBB|
    |BBBBB|     |BBBBB|              |BBBBB|BBBBB|BBBBB|
    +-----+-----+-----+              +-----+-----+-----+
    |     |BBBBB|     |   will end   |BBBBB|BBBBB|BBBBB|
    |     |BBBBB|     |   in state   |BBBBB|BBBBB|BBBBB|
    |     |BBBBB|     |              |BBBBB|BBBBB|BBBBB|
    +-----+-----+-----+              +-----+-----+-----+
    |BBBBB|BBBBB|     |              |     |     |BBBBB|
    |BBBBB|BBBBB|     |              | <-- |     |BBBBB|
    |BBBBB|BBBBB|     |              |     |     |BBBBB|
    +-----+-----+-----+              +-----+-----+-----+
.
  and
.
    +-----+-----+-----+              +-----+-----+-----+
    |BBBBB|BBBBB|BBBBB|              |     |     |BBBBB|
    |BBBBB|BBBBB|BBBBB|              |  ^  |     |BBBBB|
    |BBBBB|BBBBB|BBBBB|              |  |  |     |BBBBB|
    +-----+-----+-----+              +-----+-----+-----+
    |BBBBB|BBBBB|BBBBB|   will end   |     |BBBBB|     |
    |BBBBB|BBBBB|BBBBB|   in state   |     |BBBBB|     |
    |BBBBB|BBBBB|BBBBB|              |     |BBBBB|     |
    +-----+-----+-----+              +-----+-----+-----+
    |BBBBB|     |BBBBB|              |BBBBB|BBBBB|     |
    |BB^BB|     |BBBBB|              |BBBBB|BBBBB|     |
    |BB|BB|     |BBBBB|              |BBBBB|BBBBB|     |
    +-----+-----+-----+              +-----+-----+-----+
.
  hence
.
    +-----+-----+-----+              +-----+-----+-----+
    |BBBBB|     |BBBBB|              |BBBBB|BBBBB|BBBBB|
    |B-->B|     |BBBBB|              |BBBBB|BBBBB|BBBBB|
    |BBBBB|     |BBBBB|              |BBBBB|BBBBB|BBBBB|
    +-----+-----+-----+              +-----+-----+-----+
    |     |BBBBB|     |      is      |BBBBB|BBBBB|BBBBB|
    |     |BBBBB|     |  equivalent  |BBBBB|BBBBB|BBBBB|
    |     |BBBBB|     |      to      |BBBBB|BBBBB|BBBBB|
    +-----+-----+-----+              +-----+-----+-----+
    |BBBBB|BBBBB|     |              |BBBBB|     |BBBBB|
    |BBBBB|BBBBB|     |              |BB^BB|     |BBBBB|
    |BBBBB|BBBBB|     |              |BB|BB|     |BBBBB|
    +-----+-----+-----+              +-----+-----+-----+
(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.

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
Wikipedia, Langton's ant

Cf. A007764, A099733, A255938.

a(7) from Rok Cestnik, Aug 12 2017

A110910 Configurations in the evolution of a line of n cells in Conway's Game of Life, with 0=infinity. For periodic evolutions, a(n)=(preperiod length)+(period length). For non-periodic evolutions, a(n)=0.

Original entry on oeis.org

1, 2, 2, 2, 3, 8, 13, 15, 49, 22, 17, 17, 16, 26, 29, 41, 34, 25, 21, 26, 21, 21, 36, 31, 29, 95, 25, 29, 34, 38, 105, 150, 61, 582, 43, 58, 92, 108, 263, 277, 50, 212, 59, 53, 57, 99, 55, 170, 196, 812, 105, 54, 53, 85, 59, 81, 0, 418, 63, 63, 314, 117, 118, 170, 236, 104

Offset: 0

Paul Stoeber (pstoeber(AT)uni-potsdam.de), Oct 03 2005

If nothing catches up with an outbound glider, then a(n)=0 for n>=1000 because when you watch the horizontal 1000-line evolve in a simulator, around the 490th generation, gliders fly away from the left and right corners before the non-chaotic growing in the middle has finished, so you will see the same local picture in the 490th generation of longer lines.

			a(0)=1 because there is only the empty configuration. a(10)=2+15 because the 10-line needs two steps to become a pentadecathlon. a(56)=0 because the 56-line sends four gliders to outer space.

Berlekamp/Conway/Guy, Winning Ways ..., 2nd ed, vol. 4, chapter 25

Cf. A061342, A019473, A056605, A056614, A055397, A099733, A089520, A098720, A056613.

{- program for verification of periodic cases. The non-periodic cases listed here evolve into a periodic kernel plus gliders whose paths ahead do not intersect each other or the kernel (gliders marching in single file are not counted as intersecting). -}
import Data.Set
main = print [if n `elem` known then 0 else a n | n<-[0..105]]
known = [56, 71, 72, 75, 78, 82, 85, 86, 87, 88, 91, 92, 93, 94, 96, 98, 100, 102, 103, 105]
a n = count empty (iterate evolve (fromList [(x, 0) | x<-[1..n]]))
neighbors (x, y) = fromList
                  [(x+u, y+v) | u<-[ -1, 0, 1], v<-[ -1, 0, 1], (u, v)/=(0, 0)]
evolve life =
  let fil f = Data.Set.filter
              (\x-> f (size (life `intersection` neighbors x)))
  in (life `difference` fil (\k-> k<2 || k>3) life) `union` fil (== 3)
     (unions (Prelude.map neighbors (elems life)) `difference` life)
count o (x:xs) | x `member` o = 0
               | otherwise = 1 + count (o `union` singleton x) xs

A370776 The maximum number of alive cells reached in Conway's Game of Life when starting with the first n primes in Ulam's spiral; or -1 if no such maximum exists.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 65, 56, 120, 56, 28, 133, 30, 160, 46, 24, 24, 25, 28, 30, 31, 31, 32, 32, 32, 35, 74, 39, 38, 38, 38, 39, 40, 42, 319, 319, 319, 319, 319, 46, 129, 93, 50, 50, 72, 72, 72, 72, 72, 72, 53, 53, 56, 56, 851, 851, 167, 167, 167, 167, 391

Offset: 1

Thomas Strohmann, Mar 01 2024

nonn

The initial alive cells are at coordinates x=A214664(i), y=A214665(i) for i=1..n.
For the first 7 terms of this sequence we have a(n)=n since those initial configurations do not lead to complex enough patterns that increase the number of alive cells beyond the initial number of alive cells.
The definition includes the possibility that a glider gun (or a similar pattern) is created which will result in an unbounded number of alive cells.

			n=1 to n=4 die out very quickly (within 3 steps). The maximum number of alive cells is simply the number of alive cells in the initial pattern, i.e., n.
n=5 is the first term that leads to somewhat interesting steps in the game of life simulation (although the maximum number of alive cells still does not exceed the initial number 5):
  . . . . . | . . . . . | . . . o . | . . . o . | . . . o . | . . . . .
  o . o . . | . o o o . | . . o . o | . . o . o | . . . o . | . . . . .
  . . o o . | . . o o . | . . o . o | . . . . . | . . . . . | . . . . .
  o . . . . | . . . . . | . . . . . | . . . . . | . . . . . | . . . . .
n=8 leads to a maximum number of 65 alive cells and stabilizes after 107 steps. Initial pattern:
  o . . . o |
  . o . o . |
  o . . o o |
  . o . . . |
n=15 reaches a maximum of 160 alive cells and is the first pattern that leads to having a glider (escaping in the northeast direction). Besides the glider, the stabilized pattern contains 4 blinkers, 3 blocks, 2 beehives and 1 ship.

Wikipedia, Ulam spiral.
Wikipedia, Conway's Game of Life.

Cf. A214664, A214665.

Cf. A152389, A126803, A099733, A179412.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A110910 Configurations in the evolution of a line of n cells in Conway's Game of Life, with 0=infinity. For periodic evolutions, a(n)=(preperiod length)+(period length). For non-periodic evolutions, a(n)=0.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Haskell

A370776 The maximum number of alive cells reached in Conway's Game of Life when starting with the first n primes in Ulam's spiral; or -1 if no such maximum exists.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs