login
A263175
Number of ON cells in the one-dimensional automaton described in Comments, after n generations.
1
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.
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
KEYWORD
nonn
AUTHOR
Paul Tek, Oct 11 2015
STATUS
approved