Applying BitReverseOrder to this matrix yields a matrix which has an essentially nested form, and for size n = 2 s can be obtained from Nest[With[{c = BitReverseOrder[Range[0, Length[#] - 1]/ Length[#]]}, Flatten2D[MapIndexed[#1 {{1, 1}, {1, -1} (-1)^c 〚 Last[#2] 〛 } &, #, {2}]]] &, {{1}}, s] Using this structure, one obtains the so-called fast Fourier transform which operates in n Log[n] steps and is given by With[{n = Length[data]}, Fold[Flatten[Map[With[ {k = Length[#]/2}, {{1, 1}, {1, -1}} .

For all initial conditions this depth seems at first to increase linearly, then to decrease in a nested way according to FoldList[Plus, 0, Flatten[Table[ {1, 1, Table[-1, {IntegerExponent[i, 2] + 1}]}, {i, m}]]] This quantity alternates between value 1 at position 2 j and value j at position 2 j - j + 1 .

A single step in evolution of a general cellular automaton with state a and rule number num is then given by Map[IntegerDigits[num, k, k^Length[os]] 〚 -1 - # 〛 &, Apply[Plus, MapIndexed[k^(Length[os] - First[#2]) RotateLeft[a, #1] &, os]], {-1}] or equivalently by Map[IntegerDigits[num, k, k^Length[os]] 〚 -# - 1 〛 &, ListCorrelate[Fold[ReplacePart[k #1, 1, #2 + r + 1] &, Array[0 &, Table[2r + 1, {d}]], os], a, r + 1], {d}]

The program in the multiregister machine can be converted to a program for the 2-register machine according to RMToRM2[prog_] := Module[{segs, adrs}, segs = MapIndexed[seg, prog]; adrs = FoldList[Plus, 1, Map[Length, segs]]; MapIndexed[#1 /.

Such changes could be accounted for by changes in growth rates, but it is noteworthy that my results above on branching and folding make it clear that in general changes in growth rates can have much more dramatic effects.

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

The Thue–Morse sequence discussed on page 890 can be obtained from it by applying 1 - Mod[Flatten[Partition[FoldList[Plus, 0, list], 1, 2]], 2] (b) The n th element is simply Mod[n, 2] .

Computing powers [of numbers] The method of repeated squaring (also known as the binary power method, Russian peasant method and Pingala's method) computes the quantity m t by performing about Log[t] multiplications and building up the sequence FoldList[#1 2 m #2 &, 1, IntegerDigits[t, 2]] (related to the Horner form for the base 2 representation of t ).

The transitions between these states have probabilities given by m[Map[Length, list]] where m[s_] := With[{q = FoldList[Plus, 0, s]}, ReplacePart[ RotateRight[IdentityMatrix[Last[q]], {0, 1}], 1/Length[s], Flatten[Outer[List, Rest[q], Drop[q, -1] + 1], 1]]] The average spectrum of sequences generated according to these probabilities can be obtained by computing the correlation function for elements a distance r apart ξ [list_, r_] := With[{w = (# - Apply[Plus, #]/Length[#] &)[ Flatten[list]]}, w .

An example is testing whether one can match all possible sequences with a regular expression that involves s -fold repetitions.