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

Links

Rémy Sigrist, Table of n, a(n) for n = 0..10000

Rémy Sigrist, Representation of the iterations for n = 0..999

Rémy Sigrist, PARI program for A309441

Eric Weisstein's World of Mathematics, Elementary Cellular Automaton

Index entries for sequences related to cellular automata

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

Adjacent sequences: A309438 A309439 A309440 * A309442 A309443 A309444

Keyword

nonn

Author

Rémy Sigrist, Aug 03 2019

Status

approved