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

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, 31, 25, 19, 17, 25, 23, 13, 23, 35, 21, 39, 29, 37, 27, 35, 33, 49, 39, 29, 23, 31, 25, 27, 41, 53, 35, 49, 43, 51, 45, 25, 35, 43, 29, 39, 37, 45, 43, 15, 29, 45, 27

Offset: 0

Author

Paul Tek, Oct 11 2015

Keywords

• nonn

Comments

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

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

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

+-------------+ +-----------+

| ...0(0)0... | |\ | ...(0)... |

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

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

| ...1(0)1... | |/ | ...(0)... |

+-------------+ +-----------+

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

+-----------+-----------+

| Even pos. | Odd pos. |

+-------------+ +-----------+-----------+

| ...0(1)0... | |\ | ...(1)... | ...(0)... |

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

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

| ...1(1)1... | |/ | ...(1)... | ...(0)... |

+-------------+ +-----------+-----------+

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

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.

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

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

Examples

			After 0 generation:
- We have a unique ON cell at position z=0,
- Hence, a(0) = 1.
After 1 generation:
- ON cells appear at positions z=-1 and z=+1,
- No ON cell dies,
- Hence a(1) = a(0)+2-0 = 3.
After 2 generations:
- ON cells appears at positions z=-2 and z=+2,
- No ON cell dies,
- Hence a(2) = a(1)+2-0 = 5.
After 3 generations:
- ON cells appears at positions z=-3 and z=+3,
- ON cells at positions z=-1 and z=+1 die (as they have 2 ON neighbors),
- ON cells at positions z=-2 and z=+2 die (as they have 1 ON neighbor),
- Hence a(3) = a(2)+2-4 = 3.
Schematically:
+-----+-----------+------+
| n   | ON cells  | a(n) |
+-----+-----------+------+
|  0  |     #     |    1 |
|  1  |    ###    |    3 |
|  2  |   #####   |    5 |
|  3  |  #  #  #  |    3 |
+=====+-----------+------+
| z%2 |  1010101  |
+-----+-----------+
		

Links

• Paul Tek, Table of n, a(n) for n = 0..10000
• N. J. A. Sloane, Catalog of Toothpick and Cellular Automata Sequences in the OEIS
• Paul Tek, Illustration of the first 1000 stages
• Paul Tek, Illustration of the first 1000 stages of an equivalent 4-state cellular automaton
• Paul Tek, PERL program for this sequence
• Index entries for sequences related to cellular automata

Crossrefs

Cf. A001316.