Sierpiński pattern Other ways to generate step n of the pattern shown here in various orientations include: • Mod[Array[Binomial, {2, 2} n , 0], 2] (see pages 611 and 870 ) • 1 - Sign[Array[BitAnd, {2, 2} n , 0]] (see pages 608 and 871 ) • NestList[Mod[RotateLeft[#] + #, 2] &, PadLeft[{1}, 2 n ], 2 n - 1] (see page 870 ) • NestList[Mod[ListConvolve[{1, 1}, #, -1], 2] &, PadLeft[{1}, 2 n ], 2 n - 1] (see page 870 ) • IntegerDigits[NestList[BitXor[2#, #] &, 1, 2 n - 1], 2, 2 n ] (see page 906 ) • NestList[Mod[Rest[FoldList[Plus, 0, #]], 2] &, Table[1, {2 n }], 2 n - 1] (see page 1034 ) • Table[PadRight[ Mod[CoefficientList[(1 + x) t - 1 , x], 2], 2 n - 1], {t, 2 n }] (see pages 870 and 951 ) • Reverse[Mod[CoefficientList[Series[1/(1 - (1 + x)y), {x, 0, 2 n - 1}, {y, 0, 2 n - 1}], {x, y}], 2]] (see page 1091 ) • Nest[Apply[Join, MapThread[ Join, {{#, #}, {0 #, #}}, 2]] &, {{1}}, n] (compare page 1073 ) The positions of black squares can be found from: • Nest[Flatten[2# /. {x_, y_}  {{x, y}, {x + 1, y}, {x, y + 1}}, 1] &, {{0, 0}}, n] • Transpose[{Re[#], Im[#]}] &[ Flatten[Nest[{2 #, 2 # + 1, 2 # +  } &, {0}, n]]] (compare page 1005 ) • Position[Map[Split, NestList[Sort[Flatten[{#, # + 1}]] &, {0}, 2 n - 1]], _?(OddQ[Length[#]] &), {2}] (see page 358 ) • Flatten[Table[Map[{t, #} &, Fold[Flatten[{#1, #1 + #2}] &, 0, Flatten[2^(Position[ Reverse[IntegerDigits[t, 2]], 1] - 1)]]], {t, 2 n - 1}], 1] (see page 870 ) • Map[Map[FromDigits[#, 2] &, Transpose[Partition[#, 2]]] &, Position[Nest[{{#, #}, {#}} &, 1, n], 1] - 1] (see page 509 ) A formatting hack giving the same visual pattern is DisplayForm[Nest[SubsuperscriptBox[#, #, #] &, "1", n]]

The pictures below show what happens if one adds a number other than 1 at each step. … The first picture at the top of the facing page shows what happens if one starts with 1 and then successively multiplies by 2 at each step. … Digit sequences in base 2 of numbers obtained by starting with 1 and then successively adding a constant at each step.

mathematical fact that the area of a two-dimensional circle is π r 2 , while the volume of a three-dimensional sphere is 4/3 π r 3 , the volume of a four-dimensional hypersphere is 1/2 π 2 r 4 , and so on. … For networks that in a limiting sense correspond to ordinary d -dimensional space, this number grows like r d-1 . … Network (e) effectively has limiting dimension Log[2,3]≃1.58 .

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). For the rule on page 190 , f[z_] = 1/2 (1 -  ) {  z + 1/2, z - 1/2} . For rules (a), (b) and (c) (Koch curve) on page 191 the forms of f[z_] are respectively: (0.296 - 0.57  ) z - 0.067  - {1.04, 0.237} N[1/40 {17 ( √ 3 -  ) z, -24 + 14 z}] N[(1/2 (1/ √ 3 - 1)(  + {1, -1}) -  - (1 + {  , -  }/ √ 3 ) z)/2]

Thus, for example, any integer m can be obtained by a tree of m-1 additions of 1's such as (1 + (1 + 1)) + 1 . … In this case 6 is (1 ∘ (1 ∘ 1)) ∘ 1 , and an integer m can be obtained by Tr[1 + IntegerDigits[m, 2]] - 2 or at most Log[2, m] applications of ∘ . … It also turns out that BitXor[2a, b] + 1 works, though in this case even for 2 the smallest representation is (1 ∘ 1) ∘ (1 ∘ ((1 ∘ 1) ∘ 1)) .

Implementation [of tag systems] With the rules for case (a) on page 94 given for example by {2, {{0, 0}  {1, 1}, {1, 0}  {}, {0, 1}  {1, 0}, {1, 1}  {0, 0, 0}}} the evolution of a tag system can be obtained from TSEvolveList[{n_, rule_}, init_, t_] := NestList[If[Length[#] < n, {}, Join[Drop[#, n], Take[#, n] /. rule]]&, init, t] An alternative implementation is based on applying to the list at each step rules such as {{0, 0, s___}  {s, 1, 1}, {1, 0, s___}  {s}, {0, 1, s___}  {s, 1, 0}, {1, 1, s___}  {s, 0, 0, 0}} There are a total of ((k r + 1 - 1)/(k - 1)) k n possible rules if blocks up to length r can be added at each step and k colors are allowed.

The pictures at the top show that in case (a) stripes up to height 3 can be produced, in case (b) up to height 2, and in case (c) only up to height 1. The pictures at the bottom indicate in black for which of the 2 t + 1 successive left-hand sequences of t + 1 cells it is impossible to get stripes of respectively heights 1 and 2.

In general, however, a 1D cellular automaton rule can be given as a set of explicit replacements for all possible blocks of cells in each neighborhood (see page 60 ). Thus, for example, rule 30 can be given as {{1, 1, 1}  0, {1, 1, 0}  0, {1, 0, 1}  0, {1, 0, 0}  1, {0, 1, 1}  1, {0, 1, 0}  1, {0, 0, 1}  1, {0, 0, 0}  0} To use rules in this form, CAStep can be rewritten as CAStep[rule_, a_List] := Transpose[{RotateRight[a], a, RotateLeft[a]}] /. rule or CAStep[rule_, a_List] := Partition[a, 3, 1, 2] /. rule The rules that are given can now contain patterns, so that rule 90, for example, can be written as {{1, _, 1}  0, {1, _, 0}  1, {0, _, 1}  1, {0, _, 0}  0} But how can one set up a program that can handle rules in several different forms? … Then, for example, one can define CAStep[ElementaryCARule[rule_List], a_List] := rule 〚 8 - (RotateLeft[a] + 2 (a + 2 RotateRight[a])) 〛 CAStep[GeneralCARule[rule_, r_Integer:1], a_List] := Partition[a, 2r + 1, 1, r + 1] /. rule CAStep[FunctionCARule[f_, r_Integer:1], a_List] := Map[f, Partition[a, 2r + 1, 1, r + 1]] Note that the second two definitions have been generalized to allow rules that involve r neighbors on each side.

With all cells 0 on one step, and a block of nonzero cells on the next step, the periods are for example: {1} : 21 ; {1, 1} : 3n - 8 ; {1, 0, 1} : 666 ; {1, 1, 1} : 3n - 8 ; {1, 0, 0, 1} : irregular ( < 24n ; peaks at 6j + 1 ); {1, 0, 0, 1, 0, 1} : irregular ( ≲ 2 n ; 857727 for n= 2 6 ; 13705406 for n = 100 ).

Rules such as {{1, 0}, {0, 1}} and {{1, 1}, {0}} therefore yield repetitive behavior with sequences of limited length. … Flatten[{1, 0, CTList[{{1, 0, 0, 1}, {0, 1, 1, 0}}, {0, 1}, t]}] gives for example the Thue–Morse substitution system {1  {1, 0}, 0  {0, 1}} . … In example (d), the frequency of 1's among the first elements of sequence is approximately 3/4; {0, 0} never occurs, and the frequency of {1, 1} is approximately 1/2.