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,2

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.

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

Example

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

Crossrefs

Cf. A001316.

Sequence in context: A255313 A305883 A154800 * A137768 A137769 A029602

Adjacent sequences: A263172 A263173 A263174 * A263176 A263177 A263178

Keyword

nonn

Author

Paul Tek, Oct 11 2015

Status

approved