login
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

%I #19 Aug 04 2019 08:53:38

%S 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,

%T 12,16,12,18,12,14,16,12,16,10,8,16,12,16,20,12,16,20,12,20,16,16,24,

%U 18,24,20,16,16,16,24,24,20,20,22,24,20,32,30,20,20

%N 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).

%C We consider one-dimensional cellular automata:

%C - where each cell is either ON (black) or OFF (white),

%C - cells of (n+1)-th generation are offset by half a unit compared to cells of n-th generation, as in a honeycomb:

%C / \ / \ / \ / \

%C n-th generation ...| A | B | C | D |...

%C \ / \ / \ / \ / \

%C (n+1)-th generation ...| | E | | |...

%C \ / \ / \ / \ /

%C - 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,

%C - 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,

%C - this encoding scheme is similar to that of elementary cellular automata proposed by Stephen Wolfram.

%C This sequence is based on rule 4124:

%C - 4124 = 2^12 + 2^4 + 2^3 + 2^2,

%C - in binary, 12, 4, 3 and 2 are: "1100", "0100", "0011", and "0010",

%C - these are the patterns (ABCD) that lead to a ON cell in next generation,

%C - all other patterns lead to an OFF cell.

%C Starting from a unique ON cell, we will never have 3 consecutive ON cells in subsequent generations.

%C The ON cells form a binary tree:

%C - the two lateral branches are infinite,

%C - are there other infinite branches?

%H Rémy Sigrist, <a href="/A309441/b309441.txt">Table of n, a(n) for n = 0..10000</a>

%H Rémy Sigrist, <a href="/A309441/a309441.png">Representation of the iterations for n = 0..999</a>

%H Rémy Sigrist, <a href="/A309441/a309441.gp.txt">PARI program for A309441</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ElementaryCellularAutomaton.html">Elementary Cellular Automaton</a>

%H <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>

%F a(n) is even for any n > 0 (for symmetry reasons).

%F a(n) <= n+1 - floor((n+1)/3).

%e The first terms, alongside the corresponding generation (with dots instead of 0's and lateral 0's removed for readability), are:

%e n a(n) n-th generation

%e -- ---- ---------------

%e 0 1 1

%e 1 2 1 1

%e 2 2 1 . 1

%e 3 2 1 . . 1

%e 4 4 1 1 . 1 1

%e 5 2 1 . . . . 1

%e 6 4 1 1 . . . 1 1

%e 7 4 1 . 1 . . 1 . 1

%e 8 4 1 . . 1 . 1 . . 1

%e 9 6 1 1 . 1 . . 1 . 1 1

%e 10 4 1 . . . 1 . 1 . . . 1

%e 11 6 1 1 . . 1 . . 1 . . 1 1

%e 12 8 1 . 1 . 1 1 . 1 1 . 1 . 1

%e 13 2 1 . . . . . . . . . . . . 1

%e 14 4 1 1 . . . . . . . . . . . 1 1

%e 15 4 1 . 1 . . . . . . . . . . 1 . 1

%o (PARI) See Links section.

%Y Cf. A070952.

%K nonn

%O 0,2

%A _Rémy Sigrist_, Aug 03 2019