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

Author

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

Keywords

• nonn

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.

Examples

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

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

Crossrefs

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

Programs

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 *)

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.

Extensions

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