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.

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

Author

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

Keywords

• nonn
• uned

Comments

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.

Examples

			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.
		

References

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

Crossrefs

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

Programs

Haskell

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