3n+1 problem as cellular automaton If one writes the digits of n in base 6, then the rule for updating the digit sequence is a cellular automaton with 7 possible colors (color 6 works as an end marker that appears to the left and right of the actual digit sequence): {a_, b_, c_}  If[b  6, If[EvenQ[a], 6, 4], 3 Mod[a, 2] + Quotient[b, 2] /. 0  6 /; a  6] The 3n+1 problem can then be viewed as a question about the existence of persistent structure in this cellular automaton.

Finding primes The sieve of Eratosthenes shown in the picture is an appropriate procedure if one wants to find every prime, but testing whether an individual number is prime can be done much more efficiently, as in PrimeQ[n] in Mathematica, for example by using Fermat's so-called little theorem that Mod[a p - 1 , p]  1 whenever p is prime.

The digits of 1/n in base b repeat with period MultiplicativeOrder[b, FixedPoint[#/GCD[#, b] &, n]] which is equal to MultiplicativeOrder[b, n] for prime n , and is at most n - 1 .

The pattern generated by rule 150R has fractal dimension Log[2, 3 + Sqrt[17]] - 1 or about 1.83.

Particularly dramatic are the concatenation systems discussed on page 913 , as well as successive rows in nested patterns such as Flatten[IntegerDigits[NestList[BitXor[#, 2 #] &, 1, 500], 2]] and sequences based on numbers such as Flatten[Table[If[GCD[i, j]  0, 1, 0], {i, 1000}, {j, i}]] (see page 613 ).

1D cellular automata In a cellular automaton with k colors and r neighbors, configurations that are left invariant after t steps of evolution according to the cellular automaton rule are exactly the ones which contain only those length 2r + 1 blocks in which the center cell is the same before and after the evolution.

Properties [of second-order cellular automata] The pattern from rule 67R with simple initial conditions grows irregularly, at an average rate of about 1 cell every 5 steps. The right-hand side of the pattern from rule 173R consists three triangles that repeat progressively larger at steps of the form 2 (9 s -1) .

As discussed on page 155 , each cell here can have any gray level between 0 and 1, and at each step the gray level of a given cell is determined by averaging the gray levels of the cell and its two neighbors, adding the specified constant, and then keeping only the fractional part of the result.

The rules are of the same kind as in the previous picture, except that in the third case shown here, the gray level of each neighboring cell is multiplied by 1.13 before the average is done.

A simple example of such a universal gate is {p_, q_, 1}  {q, p, 1} —and not allowing permutations of gate inputs (or in effect wire crossings) a simple example is {p_, q_, q_}  {q, 1 - p, 1 - p} .