cp's OEIS Frontend

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

%I A263175 #20 Oct 27 2015 05:32:13
%S A263175 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 A263175 31,25,19,17,25,23,13,23,35,21,39,29,37,27,35,33,49,39,29,23,31,25,27,
%U A263175 41,53,35,49,43,51,45,25,35,43,29,39,37,45,43,15,29,45,27
%N A263175 Number of ON cells in the one-dimensional automaton described in Comments, after n generations.
%C A263175 We consider a one-dimensional automaton governed by the following rules:
%C A263175 - At stage 0, we have only one ON cell, at position z=0,
%C A263175 - An ON cell appears if it has exactly one ON neighbor:
%C A263175        +-------------+       +-----------+
%C A263175        | ...0(0)0... |   |\  | ...(0)... |
%C A263175        | ...0(0)1... | --+ \ | ...(1)... |
%C A263175        | ...1(0)0... | --+ / | ...(1)... |
%C A263175        | ...1(0)1... |   |/  | ...(0)... |
%C A263175        +-------------+       +-----------+
%C A263175 - An ON cell dies if its position and the number of its ON neighbors have a different parity:
%C A263175                              +-----------+-----------+
%C A263175                              | Even pos. | Odd pos.  |
%C A263175        +-------------+       +-----------+-----------+
%C A263175        | ...0(1)0... |   |\  | ...(1)... | ...(0)... |
%C A263175        | ...0(1)1... | --+ \ | ...(0)... | ...(1)... |
%C A263175        | ...1(1)0... | --+ / | ...(0)... | ...(1)... |
%C A263175        | ...1(1)1... |   |/  | ...(1)... | ...(0)... |
%C A263175        +-------------+       +-----------+-----------+
%C A263175 Despite these simple rules, the evolution of the number of ON cells looks quite hectic.
%C A263175 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 A263175 Apparently, we obtain the Gould's sequence (A001316) by adding the following rule:
%C A263175 - An ON cell dies if it has no ON neighbor.
%H A263175 Paul Tek, <a href="/A263175/b263175.txt">Table of n, a(n) for n = 0..10000</a>
%H A263175 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 A263175 Paul Tek, <a href="/A263175/a263175.png">Illustration of the first 1000 stages</a>
%H A263175 Paul Tek, <a href="/A263175/a263175_1.png">Illustration of the first 1000 stages of an equivalent 4-state cellular automaton</a>
%H A263175 Paul Tek, <a href="/A263175/a263175.pl.txt">PERL program for this sequence</a>
%H A263175 <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>
%e A263175 After 0 generation:
%e A263175 - We have a unique ON cell at position z=0,
%e A263175 - Hence, a(0) = 1.
%e A263175 After 1 generation:
%e A263175 - ON cells appear at positions z=-1 and z=+1,
%e A263175 - No ON cell dies,
%e A263175 - Hence a(1) = a(0)+2-0 = 3.
%e A263175 After 2 generations:
%e A263175 - ON cells appears at positions z=-2 and z=+2,
%e A263175 - No ON cell dies,
%e A263175 - Hence a(2) = a(1)+2-0 = 5.
%e A263175 After 3 generations:
%e A263175 - ON cells appears at positions z=-3 and z=+3,
%e A263175 - ON cells at positions z=-1 and z=+1 die (as they have 2 ON neighbors),
%e A263175 - ON cells at positions z=-2 and z=+2 die (as they have 1 ON neighbor),
%e A263175 - Hence a(3) = a(2)+2-4 = 3.
%e A263175 Schematically:
%e A263175 +-----+-----------+------+
%e A263175 | n   | ON cells  | a(n) |
%e A263175 +-----+-----------+------+
%e A263175 |  0  |     #     |    1 |
%e A263175 |  1  |    ###    |    3 |
%e A263175 |  2  |   #####   |    5 |
%e A263175 |  3  |  #  #  #  |    3 |
%e A263175 +=====+-----------+------+
%e A263175 | z%2 |  1010101  |
%e A263175 +-----+-----------+
%Y A263175 Cf. A001316.
%K A263175 nonn
%O A263175 0,2
%A A263175 _Paul Tek_, Oct 11 2015