As in other systems based on numbers, nested patterns are not common—though page 1160 shows how they can in principle be achieved with an equation whose solutions satisfy Mod[Binomial[x, y], 2]  1 .

The number of operations to evaluate Mod[a, b] is of order n if a has n digits and b is small.

But if IntegerDigits[x, 2] involves no consecutive 0's then for example f[x] can be obtained from 2^(b[Join[{1, 1}, #], Length[#]] &)[IntegerDigits[x, 2]] - 1 a[{l_, _}, r_] := ({l + (5r - 3#)/2, #} &)[Mod[r, 2]] a[{l_, 0}, 0] := {l + 1, 0} a[{l_, 1}, 0] := ({(13 + #(5/2)^IntegerExponent[#, 2])/6, 0} &[6l + 2] b[list_, i_] := First[Fold[a, {Apply[Plus, Drop[list, -i]], 0}, Apply[Plus, Split[Take[list, -i], #1  #2 ≠ 0 &], 1]]] (The corresponding expression for t[x] is more complicated.)

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.

Primitive recursive functions are defined to deal with non-negative integers and to be set up by combining the basic functions z = 0 & (zero), s = # + 1 & (successor) and p[i_] := Slot[i] & (projection) using the operations of composition and primitive recursion f[0, y___Integer] := g[y] f[x_Integer, y___Integer] := h[f[x - 1, y], x - 1, y] Plus and Times can then for example be defined as plus[0, y_] = y; plus[x_, y_] := s[plus[x - 1, y]] times[0, y_] = 0; times[x_, y_] := plus[times[x - 1, y], y] Most familiar integer mathematical functions also turn out to be primitive recursive—examples being Power , Mod , Binomial , GCD and Prime . … The smallest examples that show other behavior are: • r[z, r[s, s]] , which is 1/2#(# + 1)& , with quadratic growth • r[z, r[s, c[s, s]]] , which is 2 # + 1 - # - 2 & , with exponential growth • r[z, r[s, p[2]]] , which is 2^Ceiling[Log[2, # + 2]] - # - 2 & , which shows very simple nesting • r[z, r[c[s, z], z]] , which is Mod[#, 2]& , with repetitive behavior • r[z, r[s, r[s, s]]] which is Fold[1/2#1(# + 1) + #2 &, 0, Range[#]]& , growing like 2 2 x . r[z, r[s, r[s, r[s, p[2]]]]] is the first function to show significantly more complex behavior, and indeed as the picture below indicates, it already shows remarkable randomness.

It is related to the product of sawtooth functions given by Product[Abs[Mod[2 s ω , 2, -1]], {s, t}] .

Array[Apply[Times, Map[(1 - Mod[#, 2])(# - 1)!!

(d) All numbers n can be expressed as the sum of four squares, in exactly 8 Apply[Plus, Select[Divisors[n], (Mod[#, 4] ≠ 0)&]] ways, as established by Carl Jacobi in 1829.

(a_  s_)  (rtab 〚 i k + a + 1 〛  k 2r (s - 1) + 1 + Mod[i k + a, k 2r ]), {i, 0, k 2r - 1}]&, net], 1] where here elementary rule 126 is specified for example by {2, 1, Reverse[IntegerDigits[126, 2, 8]]} .

And no Turing machine of any size can directly compute a function like x 2 , 2x or Mod[x, 2] that involves manipulating all digits in x .