# Search NKS | Online

1 - 10 of 11 for FixedPointList

Lengths of [number] representations
(a) n , (b) Floor[Log[2, n] + 1] , (c) Tr[FixedPointList[Max[0, Ceiling[Log[2, #]]] &, n + 2]] - n - 3 , (d) 2 Ceiling[Log[3, 2n + 1]] , (e) Floor[Log[GoldenRatio, √ 5 (n + 1/2)]] .

Starting with a list of nodes, the nodes reached by following arcs with value a for one step are given by
NetStep[net_, i_, a_] := Union[ReplaceList[a, Flatten[net 〚 i 〛 ]]]
A list of values then corresponds to a path in the network starting from any node if
Fold[NetStep[net, #1, #2]&, Range[Length[net]], list] =!… = {}, AllNet[k], q = ISets[b = Map[Table[ Position[d, NetStep[net, #, a]] 〚 1, 1 〛 , {a, 0, k - 1}]&, d]]; DeleteCases[MapIndexed[#2 〚 2 〛 - 1 #1 &, Rest[ Map[Position[q, #] 〚 1, 1 〛 &, Transpose[Map[Part[#, Map[ First, q]]&, Transpose[b]]], {2}]] - 1, {2}], _ 0, {2}]]]
DSets[net_, k_:2] := FixedPoint[Union[Flatten[Map[Table[NetStep[net, #, a], {a, 0, k - 1}]&, #], 1]]&, {Range[Length[net]]}]
ISets[list_] := FixedPoint[Function[g, Flatten[Map[ Map[Last, Split[Sort[Part[Transpose[{Map[Position[g, #] 〚 1, 1 〛 &, list, {2}], Range[Length[list]]}], #]], First[#1] First[#2]&], {2}]&, g], 1]], {{1}, Range[2, Length[list]]}]
If net has q nodes, then in general MinNet[net] can have as many as 2 q -1 nodes. … To obtain such trimmed networks one can apply the function
TrimNet[net_] := With[{m = Apply[Intersection, Map[FixedPoint[ Union[#, Flatten[Map[Last, net 〚 # 〛 , {2}]]]&, #]&, Map[List, Range[Length[net]]]]]}, net 〚 m 〛 /.

Huffman coding
From a list p of probabilities for blocks, the list of codewords can be generated using
Map[Drop[Last[#], -1] &, Sort[ Flatten[MapIndexed[Rule, FixedPoint[Replace[Sort[#], {{p0_, i0_}, {p1_, i1_}, pi___} {{p0 + p1, {i0, i1}}, pi}] & , MapIndexed[List, p]] 〚 1, 2 〛 , {-1}]]]] -1
Given the list of codewords c , the sequence of blocks that occur in encoded data d can be uniquely reconstructed using
First[{{}, d} //.

Properties [of example symbolic system]
All initial conditions eventually evolve to expressions of the form Nest[ ℯ , ℯ , m] , which then remain fixed. … During the evolution the rule can apply only to the inner part FixedPoint[Replace[#, ℯ [x_] x] &, expr] of an expression. … It reaches a fixed point as soon as the depth reaches 0.

With this setup, a network consisting of just one node is {{1, 1}} and a 1D array of n nodes can be obtained with
CyclicNet[n_] := RotateRight[ Table[Mod[{i - 1, i + 1}, n] + 1, {i, n}]]
With above connections represented as 1 and the below connections as 2 , the node reached by following a succession s of connections from node i is given by
Follow[list_, i_, s_List] := Fold[list 〚 #1 〛 〚 #2 〛 &, i, s]
The total number of distinct nodes reached by following all possible succession of connections up to length d is given by
NeighborNumbers[list_, i_Integer, d_Integer] := Map[Length, NestList[Union[Flatten[list 〚 # 〛 ]] &, Union[list 〚 i 〛 ], d - 1]]
For each such list the rules for the network system then specify how the connections from node i should be rerouted. The rule {2, 3} {{2, 1}, {1}} specifies that when NeighborNumbers gives {2, 3} for a node i , the connections from that node should become {Follow[list, i, {2, 1}], Follow[list, i, {1}]} . … With rules set up in this way, each step in the evolution of a network system is given by
NetEvolveStep[{depth_Integer, rule_List}, list_List] := Block[ {new = {}}, Join[Table[Map[NetEvolveStep1[#, list, i] &, Replace[NeighborNumbers[list, i, depth], rule]], {i, Length[list]}], new]]
NetEvolveStep1[s : {___Integer}, list_, i_] := Follow[list, i, s]
NetEvolveStep1[{s1 : {___Integer}, s2 : {___Integer}}, list_, i_] := Length[list] + Length[ AppendTo[new, {Follow[list, i, s1], Follow[list, i, s2]}]]
The set of nodes that can be reached from node i is given by
ConnectedNodes[list_, i_] := FixedPoint[Union[Flatten[{#, list 〚 # 〛 }]] &, {i}]
and disconnected nodes can be removed using
RenumberNodes[list_, seq_] := Map[Position[seq, #] 〚 1, 1 〛 &, list 〚 seq 〛 , {2}]
The sequence of networks obtained on successive steps by applying the rules and then removing all nodes not connected to node number 1 is given by
NetEvolveList[rule_, init_, t_Integer] := NestList[(RenumberNodes[#, ConnectedNodes[#, 1]] &)[ NetEvolveStep[rule, #]] &, init, t]
Note that the nodes in each network are not necessarily numbered in the order that they appear on successive lines in the pictures in the main text.

This is a k = 8 2D cellular automaton in which toppling of sand above a critical slope is captured by updating an array of relative sand heights s according to the rule
SandStep[s_]:= s + ListConvolve[ {{0, 1, 0}, {1, -4, 1}, {0, 1, 0}}, UnitStep[s - 4], 2, 0]
Starting from any initial condition, the rule eventually yields a fixed configuration with all values less than 4, as in the picture below. … To model the pouring of sand into a pile one can consider a series of cycles, in which at each cycle one first adds 4 to the value of the center cell, then repeatedly applies the rule until a new fixed configuration FixedPoint[SandStep, s] is obtained. … With a total initial s value of m , the number of steps before a fixed point is reached seems to increase roughly like m 2 .

DNF minimization
From a table of values for a Boolean function one can immediately get a DNF representation just by listing cases where the value is 1. … Given an original DNF list s , this can be done using PI[s, n] :
PI[s_, n_] := Union[Flatten[ FixedPointList[f[Last[#], n] &, {{}, s}] 〚 All, 1 〛 , 1]]
g[a_, b_] := With[{i = Position[Transpose[{a, b}], {0,1}]}, If[Length[i] 1 && Delete[a, i] === Delete[b, i], {ReplacePart[a, _, i]}, {}]]
f[s_, n_] := With[ {w = Flatten[Apply[Outer[g, #1, #2, 1] &, Partition[Table[ Select[s, Count[#, 1] i &], {i, 0, n}], 2, 1], {1}], 3]}, {Complement[s, w, SameTest MatchQ], w}]
The minimal DNF then consists of a collection of these prime implicants. … Given the original list s and the complete prime implicant list p the so-called Quine–McCluskey procedure can be used to find a minimal list of prime implicants, and thus a minimal DNF:
QM[s_, p_] := First[Sort[Map[p 〚 # 〛 &, h[{}, Range[Length[s]], Outer[MatchQ, s, p, 1]]]]]
h[i_, r_, t_] := Flatten[Map[h[Join[i, r 〚 # 〛 ], Drop[r, #], Delete[Drop[t, {}, #], Position[t 〚 All, # 〛 ], {True}]]] &, First[Sort[Position[#, True] &, t]]]], 1]
h[i_, _, {}] := {i}
The number of steps required in this procedure can increase exponentially with the length of p .

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]] . … A simple way to approximate the pictures in the main text would be to generate patterns by iterating the substitution system a fixed number of times.

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 ).

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 ). Given two numbers x and y their product can be computed in base k by ( FromDigits does the carries)
FromDigits[ListConvolve[IntegerDigits[x, k], IntegerDigits[y, k], {1, -1}, 0], k]
For numbers with n digits direct evaluation of the convolution would take about n 2 steps. … However, the straightforward method for converting a t -digit number x to base k takes about t divisions, though this can be reduced to around Log[t] by using a recursive method such as
FixedPoint[Flatten[Map[If[# < k, #, With[ {e = Ceiling[Log[k, #]/2]}, {Quotient[#, k e ], With[ {s = Mod[#, k e ]}, If[s 0, Table[0, {e}], {Table[0, {e - Floor[Log[k, s]] - 1}], s}]]}]] &, #]] &, {x}]
The pictures below show stages in the computation of 3 20 (a) by a power tree in base 2 and (b) by conversion from base 3.