

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 nonperiodic evolutions, a(n)=0.


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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

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


REFERENCES

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


LINKS



EXAMPLE

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


PROG

(Haskell)
{ program for verification of periodic cases. The nonperiodic 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). Replace leading dots with spaces before running! }
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


CROSSREFS



KEYWORD

nonn,uned


AUTHOR

Paul Stoeber (pstoeber(AT)unipotsdam.de), Oct 03 2005


STATUS

approved



