Search NKS | Online
81 - 90 of 93 for NestList
![](/common/images/search/spacer.gif)
The sequence on step t can be obtained from Nest[Join[#, 1 - #] &, {1}, t - 1] . … The first 2 m elements in the sequence can be obtained from (see page 1081 )
(CoefficientList[Product[1 - z 2 s , {s, 0, m - 1}], z] + 1)/2
The first n elements can also be obtained from (see page 1092 )
Mod[CoefficientList[Series[(1 + Sqrt[(1 - 3x)/(1 + x)])/ (2(1 + x)), {x, 0, n - 1}], x], 2]
The sequence occurs many times in this book; it can for example be derived from a column of values in the rule 150 cellular automaton pattern discussed on page 885 .
… The resulting curve has a nested form, with envelope n^Log[3, 2] .
The pattern corresponding to each point is the limit of Nest[Flatten[1 + {c #, Conjugate[c] #}]&, {1}, n] when n ∞ . … Every point in the pattern must correspond to some list of left and right branchings, represented by 0's and 1's respectively; in terms of this list the position of the point is given by Fold[1 + {c, Conjugate[c]} 〚 1 + #2 〛 #1&, 1, Reverse[list]] .
Quadratic residue sequences
As an outgrowth of ideas related to RSA cryptography it was shown in 1982 by Lenore Blum , Manuel Blum and Michael Shub that the sequence
Mod[NestList[Mod[# 2 , m] &, x0, n], 2]
discussed on page 975 has the property that if m=p q with p and q primes (congruent to 3 modulo 4) then any systematic regularities detected in the sequence can eventually be used to discover factors of m .
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 (c), the elements are again correlated: the growth is by an average of ( √ 5 - 1)/2 ≃ 0.618 elements at each step, and the first elements on alternate steps form the same nested sequence as obtained from the substitution system {1 {1, 0}, 0 {1}} .
As an example, one can take n to be represented just by Nest[s, k, n] . … To go the other way, one uses the result that for all Church numerals x and y , Nest[s, k, n][x][y] is also a Church numeral—as can be seen recursively by noting its equality to Nest[s, k, n - 1][y][x[y]] , where as above x[y] is power[y][x] . … With n represented by Nest[k, s[k][k], n] , however, s[s[s[s]][k]][k] serves as a decrement function, and with n represented by Nest[s[s],s[k], n] , s[s[s][k]][k[k[s[s]]]] serves as a doubling function.
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] . … (Z transform or generating function methods can be applied directly only for substitution systems with rules such as {1 list, 0 1 - list} .)
(In Mathematica, the explicit form of such a tensor can be represented as a nested list for which TensorRank[list] 4 .) … If p is a list of coordinate parameters that appear in a d -dimensional metric g , then
Riemann = Table[ ∂ p 〚 j 〛 Γ 〚 i, k 〛 - ∂ p 〚 i 〛 Γ 〚 j, k 〛 + Γ 〚 i, k 〛 . … Γ 〚 i 〛 , {i, d}, {j, d}, {k, d}]
where the so-called Christoffel symbol Γ ij k is
Γ = With[{gi = Inverse[g]}, Table[Sum[ gi 〚 l, k 〛 ( ∂ p 〚 j 〛 g 〚 i, l 〛 + ∂ p 〚 i 〛 g 〚 j, l 〛 - ∂ p 〚 l 〛 g 〚 j, l 〛 ), {l, d}], {i, d}, {j, d}, {k, d}]]/2
There are d 4 elements in the nested lists for Riemann , but symmetries and the so-called Bianchi identity reduce the number of independent components to 1/12 d 2 (d 2 - 1) —or 20 for d = 4 .
(An example is NestList[Mod[2 #, 1]&, N[ π /4, 40], 200] ; Map[Precision, list] gives the number of significant digits of each element in the list.)
Other significant publications of mine providing relevant summaries were (the dates here are for actual publication—sometimes close to writing, but sometimes long delayed):
• "Computers in science and mathematics" (September 1984) ( Scientific American article about foundations of the computational approach to science and mathematics)
• "Cellular automata as models of complexity" (October 1984) ( Nature article introducing cellular automata)
• "Geometry of binomial coefficients" (November 1984) (additive cellular automata and nested patterns)
• "Twenty problems in the theory of cellular automata" (1985) (a list of unsolved problems to attack—most now finally resolved in this book)
• "Tables of cellular automaton properties" (June 1986) (features of elementary cellular automata)
• "Cryptography with cellular automata" (1986) (using rule 30 as a cryptosystem)
• "Complex systems theory" (1988) (1984 speech suggesting the research direction for the new Santa Fe Institute)
Pointer-based encoding
One can encode a list of data d by generating pointers to the longest and most recent copies of each subsequence of length at least b using
PEncode[d_, b_ : 4] := Module[{i, a, u, v}, i = 2; a = {First[d]}; While[i ≤ Length[d], {u, v} = Last[Sort[Table[{MatchLength[d, i, j], j}, {j, i - 1}]]]; If[u ≥ b, AppendTo[a, p[i - v, u]]; i += u, AppendTo[a, d 〚 i 〛 ]; i++]]; a]
MatchLength[d_, i_, j_] := With[{m = Length[d] - i}, Catch[ Do[If[d 〚 i + k 〛 =!… The encoded version of a purely nested sequence grows like Log[n] 2 .
![](/common/images/search/spacer.gif)