A263175 - OEIS

%I #20 Oct 27 2015 05:32:13

%S 1,3,5,3,7,5,9,7,9,11,15,9,15,13,13,11,11,17,25,15,25,19,19,13,21,23,

%T 31,25,19,17,25,23,13,23,35,21,39,29,37,27,35,33,49,39,29,23,31,25,27,

%U 41,53,35,49,43,51,45,25,35,43,29,39,37,45,43,15,29,45,27

%N Number of ON cells in the one-dimensional automaton described in Comments, after n generations.

%C We consider a one-dimensional automaton governed by the following rules:

%C - At stage 0, we have only one ON cell, at position z=0,

%C - An ON cell appears if it has exactly one ON neighbor:

%C        +-------------+       +-----------+

%C        | ...0(0)0... |   |\  | ...(0)... |

%C        | ...0(0)1... | --+ \ | ...(1)... |

%C        | ...1(0)0... | --+ / | ...(1)... |

%C        | ...1(0)1... |   |/  | ...(0)... |

%C        +-------------+       +-----------+

%C - An ON cell dies if its position and the number of its ON neighbors have a different parity:

%C                              +-----------+-----------+

%C                              | Even pos. | Odd pos.  |

%C        +-------------+       +-----------+-----------+

%C        | ...0(1)0... |   |\  | ...(1)... | ...(0)... |

%C        | ...0(1)1... | --+ \ | ...(0)... | ...(1)... |

%C        | ...1(1)0... | --+ / | ...(0)... | ...(1)... |

%C        | ...1(1)1... |   |/  | ...(1)... | ...(0)... |

%C        +-------------+       +-----------+-----------+

%C Despite these simple rules, the evolution of the number of ON cells looks quite hectic.

%C The automaton depicted here is not a cellular automaton, as the evolution of a particular cell involves its position. However, by considering pairs of adjacent cells (say at position 2*z and 2*z+1), it is possible to represent this automaton by a 4-state cellular automaton.

%C Apparently, we obtain the Gould's sequence (A001316) by adding the following rule:

%C - An ON cell dies if it has no ON neighbor.

%H Paul Tek, <a href="/A263175/b263175.txt">Table of n, a(n) for n = 0..10000</a>

%H N. J. A. Sloane, <a href="/wiki/Catalog_of_Toothpick_and_CA_Sequences_in_OEIS">Catalog of Toothpick and Cellular Automata Sequences in the OEIS</a>

%H Paul Tek, <a href="/A263175/a263175.png">Illustration of the first 1000 stages</a>

%H Paul Tek, <a href="/A263175/a263175_1.png">Illustration of the first 1000 stages of an equivalent 4-state cellular automaton</a>

%H Paul Tek, <a href="/A263175/a263175.pl.txt">PERL program for this sequence</a>

%H <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>

%e After 0 generation:

%e - We have a unique ON cell at position z=0,

%e - Hence, a(0) = 1.

%e After 1 generation:

%e - ON cells appear at positions z=-1 and z=+1,

%e - No ON cell dies,

%e - Hence a(1) = a(0)+2-0 = 3.

%e After 2 generations:

%e - ON cells appears at positions z=-2 and z=+2,

%e - No ON cell dies,

%e - Hence a(2) = a(1)+2-0 = 5.

%e After 3 generations:

%e - ON cells appears at positions z=-3 and z=+3,

%e - ON cells at positions z=-1 and z=+1 die (as they have 2 ON neighbors),

%e - ON cells at positions z=-2 and z=+2 die (as they have 1 ON neighbor),

%e - Hence a(3) = a(2)+2-4 = 3.

%e Schematically:

%e +-----+-----------+------+

%e | n   | ON cells  | a(n) |

%e +-----+-----------+------+

%e |  0  |     #     |    1 |

%e |  1  |    ###    |    3 |

%e |  2  |   #####   |    5 |

%e |  3  |  #  #  #  |    3 |

%e +=====+-----------+------+

%e | z%2 |  1010101  |

%e +-----+-----------+

%Y Cf. A001316.

%K nonn

%O 0,2

%A _Paul Tek_, Oct 11 2015