Given a sequence of length n , an approximation to h can be reconstructed using Max[MapIndexed[#1/First[#2] &, FoldList[Plus, First[list], Rest[list]]]] The fractional part of the result obtained is always an element of the Farey sequence Union[Flatten[Table[a/b, {b, n}, {a, 0, b}]]] (See also pages 892 , 932 and 1084 .)

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# /. … (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]]

A crucial feature of primitive recursive functions is that the number of steps they take to evaluate is always limited, and can always in effect be determined in advance, since the basic operation of primitive recursion can be unwound simply as f[x_, y___] := Fold[h[#1, #2, y] &, g[y], Range[0, x - 1]] And what this means is that any computation that for example fundamentally involves a search that might not terminate cannot be implemented by a primitive recursive function. … In enumerating recursive functions it is convenient to use symbolic definitions for composition and primitive recursion c[g_, h___] = Apply[g, Through[{h}[##]]] & r[g_, h_] = If[#1  0, g[##2], h[#0[#1 - 1, ##2], #1 - 1, ##2]] & where the more efficient unwound form is r[g_,h_] = Fold[Function[{u, v}, h[u, v, ##2]], g[##2], Range[0, #1 - 1]] & And in terms of these, for example, plus = r[p[1], s] . … From its definition, the function can be written as Fold[Fold[2^Ceiling[Log[2, Ceiling[(#1 + 2)/(#2 + 2)]]] (#2 + 2) - 2 - #1 &, #2, Range[#1]] &, 0, Range[#]]& Its first zeros are at {4, 126, 813, 966, 1166, 1177, 1666, 1897} .

[Turing] machine 596440 For any list of initial colors init , it turns out that successive rows in the first t steps of the compressed evolution pattern turn out to be given by NestList[Join[{0}, Mod[1 + Rest[FoldList[Plus, 0, #]], 2], {{0}, {1, 1, 0}} 〚 Mod[Apply[Plus, #], 2] + 1] 〛 &, init, t] Inside the right-hand part of this pattern the cell values can then be obtained from an upside-down version of the rule 60 additive cellular automaton, and starting from a sequence of 1 's the picture below shows that a typical rule 60 nested pattern can be produced, at least in a limited region.

The solution is Fold[Mod[#1 + k, #2, 1]&, 0, Range[n]] , or FromDigits[RotateLeft[IntegerDigits[n, 2]], 2] for k = 2 .

And perhaps even more important, a region may break into smaller regions that grow at different rates, and that potentially fold over or deform in other ways.

Symbolic systems [emulating cellular automata] Given the rules for an elementary cellular automaton in the form used on page 867 (with {0, 0, 0}  0 ), the following will construct a symbolic system which emulates it: Flatten[{Array[(p[x_][#1][#2][#3]  p[x[{##} /. rules]][#2][#3]) &, {2, 2, 2}, 0] /. {0  p, 1  q}, {r[x_]  p[r[p][p]][x], p[x_][p][p][r]  x[p][p][r]}}] The initial condition for the symbolic system is given by Fold[#1[#2] &, r[p][p], init /. {0  p, 1  q}][p][p][r] Step t in the cellular automaton corresponds to step t (t + Length[init] + 3) in the symbolic system.

In terms of this rule, the color of the element at position n is given by Fold[Replace[{#1, #2}, rule]&, 1, IntegerDigits[n - 1, 2]] The rule used here can be thought of as a finite automaton with two states. … Note that if the rule for the finite automaton is represented for example as {{1, 2}, {2, 1}} where each sublist corresponds to a particular state, and the elements of the sublist give the successor states with inputs Range[0, k - 1] , then the n th element in the output sequence can be obtained from Fold[rule 〚 #1, #2 〛 &, 1, IntegerDigits[n - 1, k] + 1] - 1 while the first k m elements can be obtained from Nest[Flatten[rule 〚 # 〛 ] &, 1, m] - 1 To treat examples such as case (c) where elements can subdivide into blocks of several different lengths one must generalize the notion of digit sequences.

Hump m in the picture of sequence (c) shown is given by FoldList[Plus, 0, Flatten[Nest[Delete[NestList[Rest, #, Length[#] - 1], 2]&, Append[Table[1, {m}], 0], m]] - 1/2] The first 2 m elements in the sequence can also be generated in terms of reordered base 2 digit sequences by FoldList[Plus, 1, Map[Last[Last[#]]&, Sort[Table[{Length[#], Apply[Plus, #], 1 - #}& [ IntegerDigits[i, 2]], {i, 2 m }]]]] Note that the positive and negative fluctuations in sequence (f) are not completely random: although the probability for individual fluctuations in each direction seems to be the same, the probability for two positive fluctuations in a row is smaller than for two negative fluctuations in a row.

Note that even though individual cells are pentagonal, large-scale cellular automaton patterns usually have 2-, 4- or 8-fold symmetry.) … (Large-scale cellular automaton patterns here can have 5-fold symmetry.)