OCA:Rule 120

Rule 120
x=0, y = 0, rule = W120 ! #C [[ THEME Inverse ]] #C [[ RANDOMIZE2 RANDSEED 1729 THUMBLAUNCH THUMBNAIL THUMBSIZE 2 GRID ZOOM 6 WIDTH 600 HEIGHT 600 LABEL 90 -20 2 "#G" AUTOSTART PAUSE 2 GPS 8 LOOP 256 ]] LifeViewer-generated pseudorandom soup
Number	120
Computation	p⊕(q∧r)
Character	Class 4
Black/white reversal	225
Left/right reflection	106

Rule 120 (or W120) is a 2-state 1D cellular automaton. It is notable as a class 4 rule, and for the slow growth it exhibits from the initial state of two adjacent on-cells.

Rule 225 is its black/white reversal, and exhibits the same behaviour from a one-cell state, upon inverting the background.

Definition

As in all elementary cellular automata, whether a cell in the pattern will be 0 or 1 in the new generation depends on its current value, as well as those of its two neighbours.

The Rule 120 evolution is as follows:

Current pattern	111	110	101	100	011	010	001	000
New state for center cell	0	1	1	1	1	0	0	0

The name of the rule, as in all elementary cellular automata, is the binary sequence of the new states (01111000); If interpreted as a binary number, its decimal representation is 120.

From the initial state of a single on-cell perturbation in an infinite tape of off-cells in rule 220, the on-cell's neighbourhood becomes off, but the off-cells elsewhere all change state to on. Thereafter, it emulates the behaviour of its dual, rule 120 (computed as p⊕q∧r), beginning at a pattern of three adjacent on-cells at generation 1. (The unique finite predecessor state at generation 0 has two on-cells.)

Rule 120, and rule 225 from the inverted state onwards, together with their reflections, are the unique range-1 rules that exhibit Θ(√t) growth. Consider the function l(t) (that returns the pattern's length on the tth iteration), then there are the bounds lim infn->∞(l(t)√t) = √3√2 and lim supn->∞(l(t)√t) = 3√2.

Bitwise functions

Let % denote the modulo function.

Let ¬, ∧, ⊕ and ∨ denote bitwise NOT, AND, XOR and OR, and ≪ and ≫ denote bitwise shift (n≪i = ⌊n*2ⁱ⌋ and n≫i = ⌊n2ⁱ⌋). Per , we have the descending order of precedence (-,¬),(*,/,%),(+,-),(≪,≫),(∧),(⊕),(∨) (the first two being single-input functions, negation and NOT). Unlike Python, shifts can be by negative amounts.

Per , define functions on the binary representation of n; let λ(n) = ⌊log₂(n)⌋ + 1 be the length, ρ(n) be the number of trailing 0s (the exponent of the highest power of 2 dividing n, or the 2-adic valuation of n), and ν(n) be the number of 1s (the Hamming weight of n), equivalently

ρ(0)=0; ρ(2*n)=ρ(n)+1, ρ(2*n+1)=0 . . . (A007814)

λ(0)=0; λ(2*n)=λ(n)+1, λ(2*n+1)=λ(n)+1. (A029837)

ν(0)=0; ν(2*n)=ν(n), . ν(2*n+1)=ν(n)+1. (A000120)

Consider the 'bitwise inflation' function b_n, that returns a number whose base-2ⁿ representation is the base-2 representation of its input (ie. b₂(6) = 20, since 6 = 110₂ and 20 = 110₄).

We have that lim supk->∞(b_n(k)kⁿ)=1 (with equality at powers of 2), and lim infk->∞(b_n(k)kⁿ)=12ⁿ-1 (with records preceding powers of 2).

Let c₂(n) be the characteristic function of the powers of 2 (ie. returning 1 if n is a power of 2 and 0 otherwise); we have

c₂(n) = λ(n)-λ(n-1)
      = { 1     ρ(n) = λ(n)-10 . . else
      = { 1 . . ν(n) = 10 . . else
      = { 1 . . n∧n-1 = 00 . . else

Define the floor-inverse of an integer-to-integer function f as the function g = f^-1 satisfying g(n) = min({k ∈ ℤ: f(k) = max({m ∈ ℤ: f(m) ≤ n})}). For increasing functions, the operation of floor-inversion is an involution. Similarly to how (for increasing functions over the reals) ∫₀ⁿ(f(x) dx) + ∫_f(0)^f(n)(f^-1(x) dx) = n*(f(n)-f(0)) (the basis of integration by parts), one has (with ^-1 being floor-inversion) ∑n-1k=0(f(k)) + ∑f(n)-1k=f(0)(f^-1(k)) = n*(f(n)-f(0))

Generalisations

Since the perturbation is aligned to the rightwards diagonal, one can shift it left by one cell each iteration, then it has the equivalent description "each cell flips its state if all of the 2 cells to its right are on." Fix an integer n ≥ 1, then consider the n cells to its right instead of 2. This is described by the rule in the width-n+1 neighbourhood equivalent to

f(s) = s ⊕ ∧ ni=1(s≪i)

for which the rule integer is ∑2ⁿ⁺¹-2k=2ⁿ-1(2^k) = (2²ⁿ2).

The rule emulating it upon the background state inversion is defined

f(s) = s ⊕ ¬ ∨ ni=1(s≪i)

given by rule integer ∑2ⁿ⁺¹-1k=2ⁿ+1(2^k) + 1 = (2²ⁿ-1)².

align	right		left		neighbourhood width
	stable	inverting	stable	inverting
n=2	120	225	106	169	3
sum	∑2n+1-2k=2n-1(2k)	∑2n+1-1k=2n+1(2k) + 1	∑2n-1k=1(4k)+42n-1	∑2n+1k=3(4k)+1	n+1
form	(22n2)	(22n-1)2	5*22n+1-812	22n+1-106

In the nth inverting rule, beginning with 1 on-cell in generation 0 will lead to n+1 adjacent cells being off in generation 1, against an infinite background of on cells, emulating its stable complement, which enters the same state (in which n+1 cells are on) from the generation-0 state in which n cells are on.

Hereafter, n is considered an arbitrary positive integer; all definitions given work for all rules in the series.

Let s(0) = 2ⁿ-1 and thereafter s(t) = f(s(t-1)), ie. s(t)'s binary representation is the state in the tth generation.

Since each cell's period is a factor of the lcm of those of the cells to its right, then multiplied by 2 if these cells all turn on simultaneously an odd number of times, by induction all cells' periods are powers of 2. Consider the functions

• p(k) (returning the log₂ of the period of the kth-rightmost cell) and
• d(k) (returning the log₂ of the gcd of the durations for which the cell remains in a fixed state).

The function l(t) is slow-growing, so consider its inverse function, o(k), which returns the first generation at which the kth cell turns on. The other two functions have the equivalent characterisations p(k)=λ(o(k)) and d(k)=ρ(o(k)).

Lemma: Say that j "implies" (⇒) o if it contains bits in a superset of its indexes (ie. (j ⇒ o) ⇔ (o ∧ ¬j = 0)), then for all o,j ∈ ℕ, (j ⇒ o) ⇔ (j ⇒ o+1) ⊕ (j+1 ⇒ o+1).

This can also be written with a union instead of an XOR, since the two conditions are distinct (the former if j≫ρ(o+1)∧1 = 1, the latter otherwise).

Theorem 1. s(k,t) = [t ⇒ o(k)], and for k ≥ n, o(k) = ∨ .nj=1(o(k-j)) + 1

Proof:

---

For a given cell k, assume that there exist constants o(k-1),o(k-2),...,o(k-n) for the preceding n cells such that they abide by s(k-i,t) = [t ⇒ o(k-i)]. (This is true for the first such inductive case, where k=n, the preceding cells' constants are all 0 and they are all on.)

The kth cell's state changes on generations following those at which all n neighbours are on simultaneously, so we have

. s(k,t)

= ⊕t-1j=0(∧ ni=1(s(k-i,j)))
= ⊕t-1j=0(∧ ni=1(j⇒o(k-i)))
= ⊕t-1j=0((j⇒∨ ni=1(o(k-i)))
= ⊕t-1j=0((j⇒∨ ni=1(o(k-i))+1) ⊕ (j+1⇒∨ ni=1(o(k-i))+1)
= ⊕t-1j=0((j⇒∨ ni=1(o(k-i))) ⊕ ⊕ tj=1((j⇒∨ ni=1(o(k-i)))
= (t⇒∨ ni=1(o(k-i))+1)

End proof.

---

Theorem 2. The solution to this has the exact form

o(k) = 2*(2ⁿ-1)*b_n(⌊kn+1⌋) + { 1 . . . . . . . . . . . . . .k ≡ n (mod n+1)2*(1+2^k%(n+1)-2ⁿ)*2^{ρ(⌊kn+1⌋)*n} .else

Proof:

---

In this form, the expressions to determine whether the ith bit of each term of o(k) is 1 are

2*(2ⁿ-1)*b_n(⌊kn+1⌋)≫i∧1 = ⌊kn+1⌋≫⌊i-1n⌋∧1

the term in cases is negative, so requires two's complement,

{ 1 . . . . . . . . . . . . . .k ≡ n (mod n+1)2*(1+2^k%(n+1)-2ⁿ)*2^{ρ(⌊kn+1⌋)*n} .else }≫i∧1 = { i = 0 . . . . . . . . . . . . . . . .k ≡ n (mod n+1)i-1-ρ(⌊kn+1⌋)*n ∈ {0,k%(n+1)}∪[n,∞) .else

and together,

2*(2ⁿ-1)*b_n(⌊kn+1⌋) + { 1 . . . . . . . . . . . . . .k ≡ n (mod n+1)2*(1+2^k%(n+1)-2ⁿ)*2^{ρ(⌊kn+1⌋)*n} .else }≫i∧1 = { k ≡ n (mod n+1) . . . . . . . . . . . . . . . . . . . . i = 0{ (i-1)%n = k%(n+1) . k%(n+1)<n and ⌊i-1n⌋ = ρ(⌊kn+1⌋)⌊kn+1⌋≫⌊i-1n⌋&1 . .else .else

using the recurrence relation,

o(k)-1≫i∧1 = ∨ .nj=1(o(k-j))≫i∧1 = { k !≡ n (mod n+1) . . . . . . . . . . . . . . . . . . . . . . . . . .i = 0∨ .nj=1({(i-1)%n = (k-j)%(n+1) . (k-j)%(n+1)<n and ⌊i-1n⌋ = ρ(⌊k-jn+1⌋)⌊k-jn+1⌋≫⌊i-1n⌋&1 . . . .else}) .else

Computing o(k)-1 symbolically, for the i ≠ 0 case,

We consider the case in which k ≡ n (mod n+1)

o(k)-1≫i∧1 = ∨ .nj=1({(i-1)%n = (k-j)%(n+1) . ⌊i-1n⌋ = ρ(⌊k-jn+1⌋)⌊k-jn+1⌋≫⌊i-1n⌋&1 . . . .else})

⌊k-jn+1⌋ = ⌊kn+1⌋, (k-j)%(n+1)<n is always true, and since (k-j)%(n+1) = n-j it passes through all values between 0 and n-1 exactly once, (i-1)%n = (k-j)%(n+1) is true for one OR-summand

o(k)-1≫i∧1 = (⌊i-1n⌋ = ρ(⌊kn+1⌋) or ⌊kn+1⌋≫⌊i-1n⌋∧1)

the former condition implies the latter, since for a bit's index to be the 2-adic valuation, it must be the lowest 1-bit. Thus this case's form is correct if all n preceding terms abided by the other case's

the last bit is set to 1 by the increment at the end

and in which k !≡ n (mod n+1)

since the 1-bits in the preceding k-j ≡ n (mod n+1) case are a strict superset of the 1-bits of the terms with k-j preceding it (since there can be at most n-1 of the n 'inflated' bits in the most recent b_n carry index contained before it), the OR-sum need only be considered for j ≤ k%(n+1) + 1

o(k)-1≫i∧1 = ∨k%(n+1) + 1j=1({i%n = (k-j)%(n+1) . (k-j)%(n+1)<n and ⌊in⌋ = ρ(⌊k-jn+1⌋)⌊k-jn+1⌋≫⌊in⌋&1 . . .else})

substituting j = k - j,

o(k)-1≫i∧1 = ∨k-1j=⌊kn+1⌋*(n+1)-1({i%n = j%(n+1) . j%(n+1)<n and ⌊in⌋ = ρ(⌊jn+1⌋)⌊jn+1⌋≫⌊in⌋&1 .else})

splitting the first iteration apart,

o(k)-1≫i∧1 = ⌊kn+1⌋-1≫⌊in⌋&1 ∨ ∨k-1j=⌊kn+1⌋*(n+1)({i%n = j%(n+1) . ⌊in⌋ = ρ(⌊jn+1⌋)⌊jn+1⌋≫⌊in⌋&1 .else})

in the remaining iterations, there exists a j such that i%n = j%(n+1) iff i%n < k%(n+1), and in all other cases, the fact that ⌊jn+1⌋ = ⌊kn+1⌋ enables it to be substituted to an also-iterationless form

o(k)-1≫i∧1 = ⌊kn+1⌋-1≫⌊in⌋&1 ∨ {i%n < k%(n+1) . ⌊in⌋ = ρ(⌊kn+1⌋)⌊kn+1⌋≫⌊in⌋&1 .else

the last bit of this OR is set to 1 by the preceding k ≡ n (mod n+1) case, and since b_n(x) ∨ b_n(y) = b_n(x ∨ y), bitwise ORing (2ⁿ-1)*b_n(⌊kn+1⌋-1) with (2ⁿ-1)*b_n(⌊kn+1⌋) (albeit with the new lowest 1-bit being carried to only partially 'filled') will result in all bits up to the preceding term's lowest 1-bit being filled, causing the present term to increment to a new bit in the inflated bit, 'filling' it further.

o(k)-1≫i∧1 = (⌊in⌋ < ρ(⌊kn+1⌋)) ∨ {i%n < k%(n+1) . ⌊in⌋ = ρ(⌊kn+1⌋)⌊kn+1⌋≫⌊in⌋&1 .else

End proof.

---

For n = 2, o(k) = A338888(k)

The other functions have elementary forms also,

p(k) = { 0. . . . . . . . . . . . . . . . . . . . . . . . . . . k < n1. . . . . . . . . . . . . . . . . . . . . . . . . . . k = n⌊log₂(⌊kn+1⌋)⌋*n + 1 + min(n,k+1-(n+1)*2^{⌊log₂(⌊kn+1⌋)⌋}) . k > n

and

d(k) = { 0. . . . . . . . . . . . . . . k < n or (a:=ρ(i:=⌊kn+1⌋ + ⌊k+1n+1⌋)) = 0n*(a-1) + 1 + k - ⌊(n+1)*i2⌋ . else

The state of the kth cell at the tth iteration is given by the function s(k,t) = s(t)≫k∧1,

s(k,t) = { 1 . . . . . k < nt≫d(k)∧1       t∧2^p(k)-1 ≥ o(k) and (k%(n+1)<n and c₂(⌊kn+1⌋) or s(k-(n+1)*2^{⌊log₂(⌊kn+1⌋)⌋},t) = 1)0 . . . . . else

functions over all cells

These describe facets of the state in each iteration, but their only elementary forms are recursive. v(t) and s(t) are defined in terms of two preceding terms, the one with the leading bit removed from its index, and (if the index begins with n 1s and its length's congruence modulo n is correct) the one with n leading bits removed, however following the call chain from the former for n iterations reaches the latter anyway, so it takes O(log(n)) operations to compute, assuming use of a cache.

The number of cells that are on in the tth iteration is given by v(t) = ν(s(t))

v(t) = { v(t-2^{⌊log₂(t)⌋})+1+{ v(t-(2ⁿ-1)*2^λ(t)-n)-n. t>2^n-1 and ⌊log₂(t)⌋ ≡ 0 (mod n) and t>(2ⁿ-1)*2^λ(t)-n0 . . . . . . . . . . else . t > 0n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . else

v(t) ≥ n+ν(t), with initial equalities where t ≤ 2*(2ⁿ-1).

As a sequence, v(t) cannot be expressed as a function of ν(t), since it would not be injective, except in the case of n = 1, where v(t) = 2^ν(t) = A001316(t). However, for all n, sgn(v(t)-v(t-1)) = sgn(ν(t)-ν(t-1)) = cos(π*n4)²*(2-3*cos(π*n2))

In the specific case with n = 2 and t ≥ 1, v(t) = A267592(t).

The length of the state in the tth iteration is l(t) = λ(s(t))

l(t) = { n+λ(t) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .t<2ⁿ(n+1)*2^{⌊⌊log₂(t)⌋-1n⌋}+{ { n       t<(b:=(2ⁿ-1)*2^{(⌊⌊log₂(t)⌋n⌋-1)*n+1})l(t-b). else . ⌊log₂(t)⌋ ≡ 0 (mod n)⌊log₂(t)⌋%n . . . . . . . . . . . . . . . . .else . else

The state itself as a binary number, s(t), has

s(t) = { (t+1)*2ⁿ - 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . t<2ⁿs(t-2^{⌊log₂(t)⌋})+(2^{(⌊log₂(t)⌋-1)%n}+{ s(t-b)+1-2ⁿ . ⌊log₂(t)⌋ ≡ 0 (mod n) and t≥(b:=2*(2ⁿ-1)*2^{(⌊λ(t)n⌋-1)*n})0 . . . . . . .else})*2^{(n+1)*2⌊⌊log₂(t)⌋-1n⌋} . else

For n = 2 and t ≥ 1, s(t) = A078176(t)

Other functions

Since p is a strictly increasing function, it has a floor-inverse. The first cell whose period is 2^p has index

k(p) = { 0 . . . . . . . . . . . p = 0n . . . . . . . . . . . p = 1(n+1)*2^⌊p-2n⌋ + (p-2)%n .else

Where the number of times a cell turns on during its period is given by ⌊2^c(k)⌋,

c(k) = { -1 . . . . . . . . . . .k < n.0 . . . . . . . . . . (a:=λ(i:=⌊k-nn+1⌋)-ν(i)) = 0.n*(a+1) - k + (n+1)*i. else

For the n=1 case (in which the rule produces successive rows of the Sierpinski triangle), this is equivalent to λ(k) - ρ(k) - ν(k), the number of non-trailing 0s in k's binary representation (A086784(k)), and for other n, it is obtained by a sequence morphism, from enacting the following steps upon A086784

• Multiply each element by n
• For all pairs of consecutive elements x,y with x > y, insert x-1,x-2,...,y+1 between them to conserve the property that for all k, c(k) ≥ c(k-1)-1.
• For all triplets of consecutive elements x,y,z all equal to 0, replace y with n consecutive 0s.

Note that the "density" of the kth cell (the proportion of generations for which it's on) is then given by

{ 1 . . . . . . .k < n2^{d(k)+c(k)-p(k)}. else

Bounds

2*(kn+1)ⁿ ≤ o(k), with equality where

• k < n,
• k is of the form (n+1)*2^j
• n = 1

and lim supk->∞(o(k)kⁿ) = 2*(2ⁿ-1)(n+1)ⁿ (with records occurring where k is of the form (n+1)*2^j + n).

Since 2(n+1)ⁿ ≤ o(k)kⁿ < 2*(2ⁿ-1)(n+1)ⁿ and l(o(k)) = max(n,k), l(t) ∈ Θ(ⁿ√t), with bounds (n+1)*ⁿ√tⁿ√2*(2ⁿ-1) < l(t) ≤ (n+1)*ⁿ√tⁿ√2.

Generating functions

This section contains explicit forms, characterisations and identities for the generating functions for the functions above. (Some admit more elegant definitions through these.)

Let gf be the metaoperator that takes the generating function; we capitalise the function name to denote this. F = gf(f) is defined as F(x) = ∑∞n=0(f(n)*xⁿ).

o(k)

Note that gf(b_n)(x) = ∑∞k=0(2^n*k*x^2k1+x^2k)1-x.

O(x) = 2*(2ⁿ-1)*∑∞k=0(2^n*k*x^(n+1)*2k1+x^(n+1)*2k)1-x + xⁿ1-xⁿ⁺¹ + 2*((1-2ⁿ)*(1-xⁿ)1-x + 1-(2*x)ⁿ1-2*x)*∑∞k=0(2^n*k*x^(n+1)*2k1-x^(n+1)*2k+1)

p(k)

P(x) = xⁿ + 1-xⁿ1-x*∑∞k=0(x^(n+1)*2k)1-x

k(p)

K(x) = n*x + ((n+1)*(1-xⁿ)(1-x)*(1-2*xⁿ) + x-n*xⁿ+(n-1)*xⁿ⁺¹(1-x)²*(1-xⁿ))*x²

d(k)

D(x) = 1-(n+1)*xⁿ+n*xⁿ⁺¹(1-x)²*(1-xⁿ⁺¹)*xⁿ⁺¹ + n*1-xⁿ1-x*∑∞k=0(x^(n+1)*2k1-x^(n+1)*2k)

c(k)

Note that

• A080791(k) = λ(k) - ρ(k)

gf(A086784)(x) = ∑∞k=0(x^2k+11+x^2k)1-x

• A086784(k) = λ(k) - ρ(k) - ν(k)

gf(A086784)(x) = ∑∞k=0(x^2k+1*(x-x^2k)1-x^2k+1)1-x

The individual cases may have their generating functions found separately

if k < n:

-1

1-xⁿ1-x

elif (a:=λ(i:=⌊k-nn+1⌋)-ν(i)) != 0:

n*(a+1)

n*(∑∞k=0(x^(n+1)*2k+11+x^(n+1)*2k+1)+1-(1-xⁿ⁺¹)*∑∞k=0(x^(n+1)*(2k-1))*xⁿ)1-x

(n+1)*i - k

(∑∞k=0(x^(n+1)*(2k-1))*xⁿ - xⁿ1-xⁿ⁺¹)*(x*1-xⁿ1-x + n*(1-2*xⁿ⁺¹))1-x

which add together to form the final reduced form of

C(x) = (∑∞k=0(x^{(n+1)*(2k-1)+1}*(1-xⁿ1-x - n*xⁿ1+x^(n+1)*2k)) - n - x1-x + n+11-xⁿ⁺¹)*xⁿ-11-x

functions over all cells

In the convention of lambda calculus, denote functions as expressions λ r,i: ... to be written inline in place of their name.

Define ⌿bi=a(f,r) as the nested function f(f(f(...f(f(r,a),a+1)...),b-1),b). Here, it is used only to implement forms that alternate between adding to and multiplying the accumulator, in a way that follows directly from the recurrence forms.

l(t)

Let p₀(x) = x*(1+x) and thereafter p_i+1(x) = p_i(x)*(1+x^{2*(2n-1)*2n*i})+∑nj=2(x^2n*i+j), which converges to a constant value, p_∞(x) for all |x| < 1, then L(x) = 2+p_∞(x)1-x. Equivalently,

L(x) = n + ⌿∞i=0(λ r,i: r*(1+x^{2*(2n-1)*2n*i})+∑nj=2(x^2n*i+j),x*(1+x))1-x

Let f_n(x) = ∏∞i=0(1+x^2n*i) (the g.f. of the sequence "a(k) is the number of ways to partition k into distinct powers of 2ⁿ"), then there is thus the form

L(x) = n+x*(1+x)*f_n(x^2*(2n-1))+∑∞i=0(∑nj=2(x^2n*i+j)*f_n(x^{2*(2n-1)*2n*(i+1)}))1-x

It abides by the functional identity L(x) = L(x²ⁿ)*(1-x²ⁿ)+x*(1+x)*f_n(x^2*(2n-1))+(∑n-1j=2(x^2j)-x^2*2n)*f_n(x^2*(2n-1)*2n)1-x, which uniquely defines it, together with the fact that L(0) = n.

v(t)

V(x) = ⌿∞i=0(λ r,i: ⌿n*(i+1)j=n*i+1(λ r,j: r*(1+x^2j) + x^2j*(1-x^2j)1-x,r) + (r - n*1-x^2n*i+11-x)*x^{(2n-1)*2n*i+1},n+(n+1)*x)

we may unravel the interior ⌿

. . .= ⌿∞i=0(λ r,i: r*1-x^2n*(i+1)+11-x^2n*i+1 + ∑n*(i+1)j=n*i+1(x^2j*(1-x^2n*(i+1)+1)1+x^2j)1-x + (r - n*1-x^2n*i+11-x)*x^{(2n-1)*2n*i+1},n+(n+1)*x)

and the exterior ⌿ also, to a form in conventional operators

. . .= (n+(n+1)*x)*∏∞i=0(1-x^2n*(i+1)+11-x^2n*i+1 + x^{(2n-1)*2n*i+1}) + ∑∞i=0((∑n*(i+1)j=n*i+1(x^2j*1-x^2n*(i+1)+11+x^2j)1-x - n*x^{(2n-1)*2n*i+1}*1-x^2n*i+11-x)*∏∞i=i+1(1-x^2n*(i+1)+11-x^2n*i+1 + x^{(2n-1)*2n*i+1}))

s(k,t)

Define S(x,y) as having its coefficient of x^k*y^t be s(k,t), then we have

S(x,y) = 1-xⁿ(1-x)*(1-y) + xⁿ*⌿∞i=0(λ r,i: r*1-y^2n*(i+2)+11-y^2n*(i+1)+1 + x^(n+1)*2i+1-n*(r*xⁿ*y^{(2n-1)*2n*(i+1)+1} + ∑n-1j=0(x^j*y^2n*(i+1)+1+j*1-y^2n*(i+2)+11+y^2n*(i+1)+1+j)1-y),∑nk=0(x^k*y^2k*1-y²ⁿ⁺¹1+y^2k)1-y + xⁿ⁺¹*y^2n+1-1)
. . . .= 1-xⁿ(1-x)*(1-y) + xⁿ*((∑nk=0(x^k*y^2k*1-y²ⁿ⁺¹1+y^2k)1-y + xⁿ⁺¹*y^2n+1-1)*∏∞i=0(1-y^2n*(i+2)+11-y^2n*(i+1)+1 + x^(n+1)*2i+1*y^{(2n-1)*2n*(i+1)+1}) + ∑∞i=0(x^(n+1)*2i+1-n*∑n-1j=0(x^j*y^2n*(i+1)+1+j*1-y^2n*(i+2)+11+y^2n*(i+1)+1+j)*∏∞j=i+1(1-y^2n*(j+2)+11-y^2n*(j+1)+1 + x^(n+1)*2j+1*y^{(2n-1)*2n*(j+1)+1}))1-y)

S(1,y) = V(y) and S(2,y) = S(y) (the g.f. of the monadic version that produces states as binary representations).

See also

• sqrt replicator rule, an outer-totalistic rule containing a replicator emulating a 4-state isotropic 1D rule which admits similar methods of analysis to o(k).

External links

• Rule 120 at the Wolfram Atlas of Simple Programs