In the first 200 billion digits, the frequencies of 0 through 9 differ from 20 billion by {30841, -85289, 136978, 69393, -78309, -82947, -118485, -32406, 291044, -130820} An early approximation to π was 4 Sum[(-1) k /(2k + 1), {k, 0, m}] 30 digits were obtained with 2 Apply[Times, 2/Rest[NestList[Sqrt[2 + #]&, 0, m]]] An efficient way to compute π to n digits of precision is (# 〚 2 〛 2 /# 〚 3 〛 )& [NestWhile[Apply[Function[{a, b, c, d}, {(a + b)/2, Sqrt[a b], c - d (a - b) 2 , 2 d}], #]&, {1, 1/Sqrt[N[2, n]], 1/4, 1/4}, # 〚 2 〛 ≠ # 〚 2 〛 &]] This requires about Log[2, n] steps, or a total of roughly n Log[n] 2 operations (see page 1134 ).

And with this setup, t steps of evolution can be found with SSSEvolveList[rule_, init_s, t_Integer] := NestList[(# /. rule)&, init, t] Note that as an alternative to having s be Flat , one can explicitly set up rules based on patterns such as s[x___, 1, 0, y___]  s[x, 0, 1, 0, y] .

The pattern obtained after t steps is then given by NestList[f[RotateRight[#], #]&, init, t] The pictures below show results with f being Times , and cells having values (a) {1, -1} , (b) the unit complex numbers {1,  , -1, -  } , (c) the unit quaternions. … For n = 2 , the patterns obtained are at most nested. … With a single cell seed, no pattern more complicated than nested can be obtained in such a system.

Block cellular automata With a rule of the form {{1, 1}  {1, 1}, {1, 0}  {1, 0}, {0, 1}  {0, 0}, {0, 0}  {0, 1}} the evolution of a block cellular automaton with blocks of size n can be implemented using BCAEvolveList[{n_Integer, rule_}, init_, t_] := FoldList[BCAStep[{n, rule}, #1, #2]&, init, Range[t]] /; Mod[Length[init], n]  0 BCAStep[{n_, rule_}, a_, d_] := RotateRight[ Flatten[Partition[RotateLeft[a, d], n]/.rule], d] Starting with a single black cell, none of the k = 2 , n = 2 block cellular automata generate anything beyond simple nested patterns.

Random walks In one dimension, a random walk with t steps of length 1 starting at position 0 can be generated from NestList[(# + (-1)^Random[Integer])&, 0, t] or equivalently FoldList[Plus, 0, Table[(-1)^Random[Integer], {t}]] A generalization to d dimensions is then FoldList[Plus, Table[0, {d}], Table[RotateLeft[PadLeft[ {(-1)^Random[Integer]}, d], Random[Integer, d - 1]], {t}]] A fundamental property of random walks is that after t steps the root mean square displacement from the starting position is proportional to √ t . … As mentioned on page 1082 , the frequency spectrum Abs[Fourier[list]] 2 for a 1D random walk goes like 1/ ω 2 . … To make a random walk on a lattice with k directions in two dimensions, one can set up e = Table[{Cos[2 π s/k], Sin[2 π s/k]}, {s, 0, k - 1}] then use FoldList[Plus, {0, 0}, Table[e 〚 Random[Integer, {1, k}] 〛 , {t}]] It turns out that on any regular lattice, in any number of dimensions, the average behavior of a random walk is always isotropic.

Continued fractions The first n terms in the continued fraction representation for a number x can be found from the built-in Mathematica function ContinuedFraction , or from Floor[NestList[1/Mod[#, 1]&, x, n - 1]] A rational approximation to the number x can be reconstructed from the continued fraction using FromContinuedFraction or by Fold[(1/#1 + #2 )&, Last[list], Rest[Reverse[list]]] The pictures below show the digit sequences of successive iterates obtained from NestList[1/Mod[#, 1]&, x, n] for several numbers x . … As discovered by Jeffrey Shallit in 1979, numbers of the form Sum[1/k 2 i , {i, 0, ∞ }] that have nonzero digits in base k only at positions 2 i turn out to have continued fractions with terms of limited size, and with a nested structure that can be found using a substitution system according to {0, k - 1, k + 2, k, k, k - 2, k, k + 2, k - 2, k} 〚 Nest[Flatten[{{1, 2}, {3, 4}, {5, 6}, {7, 8}, {5, 6}, {3, 4}, {9, 10}, {7, 8}, {9, 10}, {3, 4}} 〚 # 〛 ]&, 1, n] 〛 The continued fractions for square roots are always periodic; for higher roots they never appear to show any significant regularities.

Implementation [of basic aggregation model] One way to represent a cluster is by giving a list of the coordinates at which each black cell occurs. Then starting with a single black cell at the origin, represented by {{0, 0}} , the cluster can be grown for t steps as follows: AEvolve[t_] := Nest[AStep, {{0, 0}}, t] AStep[c_] := If[!… With a grid of cells set up in advance, each step in this type of Eden model can be achieved with AStep[a_] := ReplacePart[a, 1, (# 〚 Random[ Integer, {1, Length[#]}] 〛 &)[Position[(1 - a)Sign[ ListConvolve[{{0, 1, 0}, {1, 0, 1}, {0, 1, 0}}, a, {2, 2}]], 1]]] This implementation can readily be extended to generalized aggregation models (see below ).

Implementation [of geometric substitution systems] The most convenient approach is to represent each pattern by a list of complex numbers, with the center of each square being given in terms of each complex number z by {Re[z], Im[z]} . The pattern after n steps is then given by Nest[Flatten[f[#]] &, {0}, n] , where for the rule on page 189 f[z_] = 1/2 (1 -  ) {z + 1/2, z - 1/2} ( f[z_] = (1 -  ){z + 1, z} gives a transformed version).

In a typical case, each cell is updated using LFSRStep[list_] := Append[Rest[list], Mod[list 〚 1 〛 + list 〚 2 〛 , 2]] with a step of cellular automaton evolution corresponding to the result of updating all cells in the register. … The pictures below show the evolution obtained for n = 30 with NestList[Nest[LFSRStep, #, n]&, Append[Table[0, {n - 1}], 1], t] Like additive cellular automata as discussed on page 951 , states in a linear feedback shift register can be represented by a polynomial FromDigits[list, x] . … Such generators are directly related to linear feedback shift registers, since with a list of length q , each step is simply Append[Rest[list], Mod[list 〚 1 〛 + list 〚 q - p + 1 〛 , 2 k ]] Cryptographic generators.

(Notably, FoldList normally seems more difficult to understand than NestList .)