The plot is on a logarithmic scale, so the height of each point is essentially the length of the digit sequence for the number that it represents—or the width of the row on the left.

In the case of rational numbers, the results are always of limited length.

(d) The length of the sequence at step t satisfies a[t]  2a[t - 1] + a[t - 2] , so that a[t] = Round[(1 + √ 2 ) t - 1 /2] for t > 1 . … Much like example (c) on page 83 there are m + 1 distinct blocks of length m , and with f = Floor[(1 - 1/ √ 2 )(# + 1/ √ 2 )] & the n th element of the sequence is given by f[n + 1] - f[n] (see page 903 ).

It is related to (a) by Gray code reordering of the rows, and to (b) by reordering according to (see page 905 ) BitReverseOrder[a_] := With[{n = Length[a]}, a 〚 Map[FromDigits[Reverse[#], 2] &, IntegerDigits[Range[0, n - 1], 2, Log[2, n]]] + 1 〛 ] It is also given by Array[Apply[Times, (-1)^(IntegerDigits[#1, 2, s] Reverse[IntegerDigits[#2, 2, s]])] &, 2^{s,s}, 0] where (b) is obtained simply by dropping the Reverse . … Direct evaluation of this for length n takes n 2 steps. However, the nested structure of m in natural order allows evaluation in only about n Log[n] steps using Nest[Flatten[Transpose[Partition[#, 2] . {{1, 1}, {1, -1}}]] &, data, Log[2, Length[data]]] This procedure is similar to the fast Fourier transform discussed below.

(In some cases it works to look at whether the limiting ratio of lengths on successive steps is a Pisot number.) … With k colors each giving a string of the same length s the recurrence relation is Thread[Map[ ϕ [#][t + 1, ω ] &, Range[k] - 1]  Apply[Plus, MapIndexed[Exp[  ω (Last[#2] - 1) s t ] ϕ [#1][t, ω ] &, Range[k] - 1 /. rules, {-1}], {1}]/ √ s ] Some specific properties of the examples shown include: (a) (Thue–Morse sequence) The spectrum is essentially Nest[Range[2 Length[#]] Join[#, Reverse[#]] &, {1}, t] .

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 . In general, the probability distribution for the displacement of a particle that executes a random walk is With[{ σ = 1}, (d/(2 π σ t)) d/2 Exp[-d r 2 /(2 σ t)]] The same results are obtained, with a different value of σ , for other random microscopic rules, so long as the variance of the distribution of step lengths is bounded (as in the Central Limit Theorem). … As discussed in the note below, this can be viewed as a consequence of the fact that the probability distribution in a random walk depends only on Sum[Outer[Times, e 〚 s 〛 , e 〚 s 〛 ], {s, Length[e]}] and not on products of more of the e 〚 s 〛 .

In general a length n list can require about n steps.

The pictures below show a few sequences of pair comparisons that sort lists of length n = 16 . … For n ≤ 8 the Batcher method is known to give minimal length sequences of comparisons (for n ≤ 5 the total numbers of minimal sequences that work are {1, 6, 3, 13866} ).

In the limit, such sequences contain with equal frequency all possible blocks of any given length, but as shown on page 597 , they exhibit other obvious deviations from randomness. The picture below shows the k = 2 sequence chopped into length 256 blocks.

Fibonacci[n] can be obtained in many ways: • (GoldenRatio n - (-GoldenRatio) -n )/ √ 5 • Round[GoldenRatio n / √ 5 ] • 2 1 - n Coefficient[(1 + √ 5 ) n , √ 5 ] • MatrixPower[{{1, 1}, {1, 0}}, n - 1] 〚 1, 1 〛 • Numerator[NestList[1/(1 + #)&, 1, n]] • Coefficient[Series[1/(1 - t - t 2 ), {t, 0, n}], t n - 1 ] • Sum[Binomial[n - i - 1, i], {i, 0, (n - 1)/2}] • 2 n - 2 - Count[IntegerDigits[Range[0, 2 n - 2 ], 2], {___, 1, 1, ___}] A fast method for evaluating Fibonacci[n] is First[Fold[f, {1, 0, -1}, Rest[IntegerDigits[n, 2]]]] f[{a_, b_, s_}, 0] = {a (a + 2b), s + a (2a - b), 1} f[{a_, b_, s_}, 1] = {-s + (a + b) (a + 2b), a (a + 2b), -1} Fibonacci numbers appear to have first arisen in perhaps 200 BC in work by Pingala on enumerating possible patterns of poetry formed from syllables of two lengths. … In addition: • GoldenRatio is the solution to x  1 + 1/x or x 2  x + 1 • The right-hand rectangle in is similar to the whole rectangle when the aspect ratio is GoldenRatio • Cos[ π /5]  Cos[36 ° ]  GoldenRatio/2 • The ratio of the length of the diagonal to the length of a side in a regular pentagon is GoldenRatio • The corners of an icosahedron are at coordinates Flatten[Array[NestList[RotateRight, {0, (-1) #1 GoldenRatio, (-1) #2 }, 3]&, {2, 2}], 2] • 1 + FixedPoint[N[1/(1 + #), k] &, 1] approximates GoldenRatio to k digits, as does FixedPoint[N[Sqrt[1 + #],k]&, 1] • A successive angle difference of GoldenRatio radians yields points maximally separated around a circle (see page 1006 ).