login
A309441
Number of ON (black) cells in the n-th iteration of the "honeycomb" elementary cellular automaton with rule 4124, starting with a single ON (black) cell (see Comments for precise definition).
1
1, 2, 2, 2, 4, 2, 4, 4, 4, 6, 4, 6, 8, 2, 4, 4, 4, 8, 4, 8, 8, 8, 12, 8, 12, 14, 4, 8, 8, 6, 12, 8, 12, 16, 12, 18, 12, 14, 16, 12, 16, 10, 8, 16, 12, 16, 20, 12, 16, 20, 12, 20, 16, 16, 24, 18, 24, 20, 16, 16, 16, 24, 24, 20, 20, 22, 24, 20, 32, 30, 20, 20
OFFSET
0,2
COMMENTS
We consider one-dimensional cellular automata:
- where each cell is either ON (black) or OFF (white),
- cells of (n+1)-th generation are offset by half a unit compared to cells of n-th generation, as in a honeycomb:
/ \ / \ / \ / \
n-th generation ...| A | B | C | D |...
\ / \ / \ / \ / \
(n+1)-th generation ...| | E | | |...
\ / \ / \ / \ /
- each cell of (n+1)-th generation is determined by the pattern formed by 4 neighboring cells of n-th generation: the state of cell E is determined by the pattern ABCD,
- if we represent ON cells by 1's and OFF cells by 0's, then we can uniquely represent the set of 16 rules that defines such an automaton by an integer R in the range 0..2^16-1,
- this encoding scheme is similar to that of elementary cellular automata proposed by Stephen Wolfram.
This sequence is based on rule 4124:
- 4124 = 2^12 + 2^4 + 2^3 + 2^2,
- in binary, 12, 4, 3 and 2 are: "1100", "0100", "0011", and "0010",
- these are the patterns (ABCD) that lead to a ON cell in next generation,
- all other patterns lead to an OFF cell.
Starting from a unique ON cell, we will never have 3 consecutive ON cells in subsequent generations.
The ON cells form a binary tree:
- the two lateral branches are infinite,
- are there other infinite branches?
FORMULA
a(n) is even for any n > 0 (for symmetry reasons).
a(n) <= n+1 - floor((n+1)/3).
EXAMPLE
The first terms, alongside the corresponding generation (with dots instead of 0's and lateral 0's removed for readability), are:
n a(n) n-th generation
-- ---- ---------------
0 1 1
1 2 1 1
2 2 1 . 1
3 2 1 . . 1
4 4 1 1 . 1 1
5 2 1 . . . . 1
6 4 1 1 . . . 1 1
7 4 1 . 1 . . 1 . 1
8 4 1 . . 1 . 1 . . 1
9 6 1 1 . 1 . . 1 . 1 1
10 4 1 . . . 1 . 1 . . . 1
11 6 1 1 . . 1 . . 1 . . 1 1
12 8 1 . 1 . 1 1 . 1 1 . 1 . 1
13 2 1 . . . . . . . . . . . . 1
14 4 1 1 . . . . . . . . . . . 1 1
15 4 1 . 1 . . . . . . . . . . 1 . 1
PROG
(PARI) See Links section.
CROSSREFS
Cf. A070952.
Sequence in context: A064129 A005137 A222959 * A220498 A330772 A105681
KEYWORD
nonn
AUTHOR
Rémy Sigrist, Aug 03 2019
STATUS
approved