A138277 Total number of active nodes of the Rule 150 cellular automaton on an infinite Bethe lattice with coordination number 4 (with a single 1 as initial condition).

1, 5, 13, 49, 109, 473, 1081, 4037, 8749, 37913, 88465, 325021, 717337, 3108461, 7095613, 26490289, 57395629, 248714393, 580333585, 2132141341, 4707150193, 20397650837, 46548642709, 173816036825, 376630110937, 1632063814061, 3808148899477, 13991111158153

Offset

0,2

Comments

See A138276 for the corresponding sequence for a Bethe lattice with coordination number 3.

See A001045 for the corresponding sequence on a 1D lattice (equivalent to a k=2 Bethe lattice); this is based on the Jacobsthal sequence A001045.

See A072272 for the corresponding sequence on a 2D lattice (based on A007483).

Related to Cellular Automata.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..1000

Jens Christian Claussen, Time-evolution of the Rule 150 cellular automaton activity from a Fibonacci iteration [broken link]

Jens Christian Claussen, Time-evolution of the Rule 150 cellular automaton activity from a Fibonacci iteration, arXiv:math.CO/0410429.

Jan Nagler and Jens Christian Claussen (2005), 1/f^alpha spectra in elementary cellular automata and fractal signals, Phys. Rev. E 71 (2005), 067103

Formula

The total number of nodes in state 1 after n iterations (starting with a single 1) of the Rule 150 cellular automaton on an infinite Bethe lattice with coordination number 4. Rule 150 sums the values of the focal node and its k neighbors, then applies modulo 2.

Example

Let x_0 be the state (0 or 1) of the focal node and x_i the state of every node that is i steps away from the focal node. In time step n=0, all x_i=0 except x_0=1 (start with a single seed). In the next step, x_1=1 as they have 1 neighbor being 1. For n=2, the x_1 nodes have 1 neighbor being 1 (x_0) and themselves being 1; the sum being 2, modulo 2, resulting in x_1=0.
The focal node and outmost nodes x_n are always 1.
Thus one has the patterns
x_0, x_1, x_2, ...
1
1 1
1 0 1
1 0 1 1
1 0 0 0 1
1 1 0 1 1 1
1 0 0 0 1 0 1
1 1 0 1 1 0 1 1
1 0 0 0 0 0 0 0 1
(N.B.: This is equivalent to the right half plane of Rule 150 in 1D.)
The nodes have the multiplicities 1,4,12,36,108,324,972,...
The sequence then is obtained by
a(n)= x_0(n) + 4*(x_1(n) + sum_(i=2...n) x_i(n) * 3^(i-1)).

Mathematica

nmax = 30;
states = CellularAutomaton[150, {{1}, 0}, nmax];
T[n_, i_] := states[[n+1, nmax+i+1]];
a[n_] := T[n, 0] + 4(T[n, 1]+Sum[3^(i-1) T[n, i], {i, 2, n}]);
Table[a[n], {n, 0, nmax}] (* Jean-François Alcover, Aug 20 2018 *)

Crossrefs

Cf. A138276, A072272, A007483, A071053, A001045.

Sequence in context: A146152 A082132 A220900 * A343549 A084601 A149532

Adjacent sequences: A138274 A138275 A138276 * A138278 A138279 A138280

Keyword

nonn

Author

Jens Christian Claussen (claussen(AT)theo-physik.uni-kiel.de), Mar 11 2008

Extensions

a(9)-a(27) from Alois P. Heinz, Jun 28 2015

Status

approved