Algebraic forms [for cellular automaton rules] The rules here can be expressed in algebraic terms (see page 869 ) as follows: • Rule 22: Mod[p + q + r + p q r, 2] • Rule 60: Mod[p + q, 2] • Rule 105: Mod[1 + p + q + r, 2] • Rule 129: Mod[1 + p + q + r + p q + q r + p r, 2] • Rule 150: Mod[p + q + r, 2] • Rule 225: Mod[1 + p + q + r + q r, 2] Note that rules 60, 105 and 150 are additive, like rule 90.

What is behind this is that each of the numbers in the basic sequence here must be a so-called quadratic residue of the form Mod[v 2 , m] , and given any such quadratic residue x the expression GCD[x + Mod[x 2 , m], m] turns out always to be a factor of m —and at least sometimes a non-trivial one. … If m is a prime p , then the simple tests JacobiSymbol[x, p]  1 (see page 1081 ) or Mod[x (p - 1)/2 , p]  1 determine whether x is a quadratic residue. … The condition Mod[p, 4]  Mod[q, 4]  3 ensures that only one of the solutions +v and -v to x  Mod[v 2 , m] is ever a quadratic residue, with the result that the iterated mapping x  Mod[x 2 , m] always has a unique inverse.

Non-periodic pattern [forced by 2D constraint] The color at position x, y in the pattern is given by a[x_, y_] := Mod[y + 1, 2] /; x + y > 0 a[x_, y_] := 0 /; Mod[x + y, 2]  1 a[x_, y_] := Mod[Floor[(x - y) 2 (x + y - 6)/4 ], 2] /; Mod[x + y, 4]  2 a[x_, y_] := 1 - Sign[Mod[x - y + 2, 2 (-x - y + 8)/4 ]] The origin of the x, y coordinates is the only freedom in this pattern.

Algebraic forms [for cellular automaton rules] The rules here can be expressed in algebraic terms (see page 869 ) as follows: • Rule 30: Mod[p + q + r + q r, 2] • Rule 45: Mod[1 + p + r + q r, 2] • Rule 73: Mod[1 + p + q + r + p r + p q r, 2]

Powers of 3/2 The n th value shown in the plot here is Mod[(3/2) n , 1] . … In base 6, (3/2) n is a cellular automaton with rule {a_, b_, c_}  3 Mod[a + Quotient[b, 2], 2] + Quotient[3 Mod[b, 2] + Quotient[c, 2], 2] (Note that this rule is invertible.) … In general, it seems that Mod[u (3/2) n , 1] can be kept as large as about 0.30 (e.g. with u = 0.38906669065... ) but no larger.

An element m in a message is encoded as c = PowerMod[m, d, n] . It can then be decoded as PowerMod[c, e, n] , where e = PowerMod[d, -1, EulerPhi[n]] .

Given only an output list NestList[Mod[a #, m]&, x, n] parameters {a, m} that generate the list can be found for sufficiently large n from With[{ α = Apply[(#2 . Rest[list]/#1) &, Apply[ ExtendedGCD, Drop[list, -1]]]}, {Mod[ α , #], #} &[ Fold[GCD[#1, If[#1  0, #2, Mod[#2, #1]]] &, 0, ListCorrelate[{ α , -1}, list]]]] With slightly more effort both x and {a, m} can be found just from First[IntegerDigits[list, 2, p]] .

Properties [of example Turing machines] The maximum numbers of steps increase with input size according to: (a) 14 2^Floor[n/2] - 11 + 2Mod[n, 2] (b) (does not halt for x = 1 ) (c) 2 n - 1 (d) (7(1 + Mod[n, 2])4^Floor[n/2] + 2Mod[n, 2] - 7)/3 (h) (see note below) (i) (does not halt for various x > 53 ) (j) (does not halt for various x > 39 ) (k) (does not halt for x = 1 ) (l) 5 (2 n - 2 - 1)

General powers [of numbers] It has been known in principle since the 1930s that Mod[h n , 1] is uniformly distributed in the range 0 to 1 for almost all values of h . … Exceptions are known to include so-called Pisot numbers such as GoldenRatio , √ 2 + 1 and Root[# 3 - # - 1 &, 1] (the numerically smallest of all Pisot numbers) for which Mod[h n , 1] becomes 0 or 1 for large n . Note that Mod[x h n , 1] effectively extracts successive digits of x in base h (see pages 149 and 919 ).

Given p = Array[Prime, Length[list], PrimePi[Max[list]] + 1] or any list of integers that are all relatively prime and above Max[list] (the integers in list are assumed positive) CRT[list_, p_] := With[{m = Apply[Times, p]}, Mod[Apply[Plus, MapThread[#1 (m/#2)^EulerPhi[#2] &, {list, p}]], m]] yields a number x such that Mod[x, p]  list . Based on this LE[list_] := Module[{n = Length[list], i = Max[MapIndexed[ #1 - #2 &, PrimePi[list]]] + 1}, CRT[PadRight[ list, n + i], Join[Array[Prime[i + #] &, n], Array[Prime, i]]]] will yield a number x that can be decoded into a list of length n using essentially the so-called Gödel β function Mod[x, Prime[Rest[NestList[NestWhile[# + 1 &, # + 1, Mod[x, Prime[#]]  0 &] &, 0, n]]]]