The Ulam–Warburton cellular automaton (UWCA) is a 2-dimensional fractal pattern that grows on a regular grid of cells consisting of squares. Starting with one square initially ON and all others OFF, successive iterations are generated by turning ON all squares that share precisely one edge with an ON square. This is the von Neumann neighborhood. The automaton is named after the Polish-American mathematician and scientist Stanislaw Ulam and the Scottish engineer, inventor and amateur mathematician Mike Warburton.
Properties and relations The UWCA is a 2D 5-neighbor outer totalistic cellular automaton using rule 686. The number of cells turned ON in each iteration is denoted u ( n ) , {\displaystyle u(n),} with an explicit formula:
u ( 0 ) = 0 , u ( 1 ) = 1 , {\displaystyle u(0)=0,u(1)=1,} and for n ≥ 2 {\displaystyle n\geq 2}
u ( n ) = 4 ⋅ 3 w t ( n − 1 ) − 1 {\displaystyle u(n)=4\cdot 3^{wt(n-1)-1}}
where w t ( n ) {\displaystyle wt(n)} is the Hamming weight function which counts the number of 1's in the binary expansion of n {\displaystyle n}
w t ( n ) = n − ∑ k = 1 ∞ ⌊ n 2 k ⌋ {\displaystyle wt(n)=n-\sum _{k=1}^{\infty }\left\lfloor {\frac {n}{2^{k}}}\right\rfloor }
The minimum upper bound of summation for k {\displaystyle k} is such that 2 k ≥ n {\displaystyle 2^{k}\geq n}
The total number of cells turned ON is denoted U ( n ) {\displaystyle U(n)}
U ( n ) = ∑ i = 0 n u ( i ) = 4 3 ∑ i = 0 n − 1 3 w t ( i ) − 1 3 {\displaystyle U(n)=\sum _{i\mathop {=} 0}^{n}u(i)={\frac {4}{3}}\sum _{i\mathop {=} 0}^{n-1}3^{wt(i)}-{\frac {1}{3}}}
Table of wt(n), u(n) and U(n) The table shows that different inputs to w t ( n ) {\displaystyle wt(n)} can lead to the same output. This surjective property emerges from the simple rule of growth – a new cell is born if it shares only one-edge with an existing ON cell - the process appears disorderly and is modeled by functions involving w t ( n ) {\displaystyle wt(n)} but within the chaos there is regularity.
U ( n ) {\displaystyle U(n)} is OEIS sequence A147562 and u ( n ) {\displaystyle u(n)} is OEIS sequence A147582
Counting cells with quadratics
For all integer sequences of the form n m = m ⋅ 2 k {\displaystyle n_{m}=m\cdot 2^{k}} where m ≥ 1 {\displaystyle m\geq 1} and k ≥ 0 {\displaystyle k\geq 0}
Let
a m = ∑ i = 0 m − 1 3 w t ( i ) {\displaystyle a_{m}=\sum _{i\mathop {=} 0}^{m-1}3^{wt(i)}}
( a m {\displaystyle a_{m}} is OEIS sequence A130665) Then the total number of ON cells in the integer sequence n m {\displaystyle n_{m}} is given by
U m ( n m ) = a m m 2 4 3 n m 2 − 1 3 {\displaystyle U_{m}(n_{m})={\frac {a_{m}}{m^{2}}}{\frac {4}{3}}n_{m}^{2}-{\frac {1}{3}}}
… excerpt ends here. Continue reading the full article.
