These values can be found using the so-called Lucas-Lehmer test Nest[Mod[# 2 - 2, 2 n - 1] &, 4, n - 2]  0 , and in all cases n itself must be prime. … It is known that any odd perfect number must be greater than 10 300 , must have a factor of at least 10 6 , and must be less than 4 4 s if it has only s prime factors. … For odd n up to 500 million the only values near 0 that appear in the curve are {-6, -5, -4, -2, -1, 6, 18, 26, 30, 36} , with, for example, the first 6 occurring at n = 8925 and last 18 occurring at n = 159030135 .

But one can for example also look at rules that involve three colors, rather than two, so that cells can not only be black and white, but also gray. … The idea of a totalistic rule is to take the new color of each cell to depend only on the average color of neighboring cells, and not on their individual colors. … With 0 representing white, 1 gray and 2 black, the rightmost element of the rule gives the result for average color 0, while the element immediately to its left gives the result for average color 1/3—and so on.

Connection [of 2D substitution systems] with digit sequences Just as in the 1D case discussed on page 891 , the color of a cell at position {i, j} in a 2D substitution system can be determined using a finite automaton from the digit sequences of the numbers i and j . At step n , the complete array of cells is Table[If[FreeQ[Transpose[IntegerDigits[{i, j}, k, n]], form], 1, 0], {i, 0, k n - 1}, {j, 0, k n - 1}] where for the pattern on page 187 , k = 2 and form = {0, 1} . For patterns (a) through (f) on page 188 , k = 3 and form is given respectively by (a) {1, 1} , (b) {0 | 2, 0 | 2} , (c) {0 | 2, 0 | 2} | {1, 1} , (d) {i_, j_} /; j > i , (e) {0, 2} | {1, 1} | {2, 0} , (f) {0, 2} | {1, 1} .

Binary decision diagrams One can specify a Boolean function of n variables by giving a finite automaton (and thus a network) in which paths exist only for those lists of values for which the function yields True . … Out of all possible Boolean functions the number that require BDDs of sizes 1, 2, ... is for n = 2 : {1, 0, 6, 9} and for n = 3 : {1, 0, 0, 27, 36, 132, 60} ; the absolute maximum grows roughly like 2 n . … For rule 254, for example, it is 8t + 2 , while for rule 90 it is 4t + 2 .

But as discussed on page 786 , nothing similar is true for equations involving only integers, and in this case finding solutions can in effect require following the evolution of a system like a cellular automaton for infinitely many steps. If one allows trigonometric functions, any equation for integers can be converted to one for real numbers; for example x 2 + y 2  z 2 for integers is equivalent to Sin[ π x] 2 + Sin[ π y] 2 + Sin[ π z] 2 + (x 2 + y 2 - z 2 ) 2  0 for real numbers.

Note the inequality 1 ≤ DigitCount[n, 2, 1] ≤ Log[2, n] . … , 2] and 2n - Log[2, Denominator[Derivative[n][(1 - #) -1/2 &][0]/n!]] Straightforward generalizations of DigitCount can be defined for integer and non-integer bases and by looking not only at the total number of digits but also at correlations between digits.

Representing repetitive [2D] patterns Repetitive patterns are often most conveniently represented as tessellations of rectangles whose corners overlap. Pattern (a) on page 213 can be specified as {{2, -1, 2, 3}, {{0, 0, 0, 0}, {1, 1, 0, 0}, {1, 0, 0, 0}}} Given this, a complete nx by ny array filled with this pattern can be constructed from c[{d1_, d2_, d3_, d4_}, {x_, y_}] := With[{d = d1 d2 + d1 d4 + d3 d4}, Mod[{{d2 x + d4 x + d3 y, d4 x - d1 y}}/d, 1]] Fill[{dlist_, data_}, {nx_, ny_}] := Array[c[dlist, {##}] &, {nx, ny}] /. Flatten[MapIndexed[ c[dlist, Reverse[#2]]  #1 &, Reverse[data], {2}], 1]

Rule 60 Turing machines One can emulate rule 60 using the 8-case s = 3 , k = 3 Turing machine (with initial condition Append[list + 1, 1] surrounded by 0 's) {{1, 2}  {2, 2, 1}, {1, 1}  {1, 1, 1}, {1, 0}  {3, 1, -1}, {2, 2}  {2,1, 1}, {2, 1}  {1, 2, 1}, {3, 2}  {3, 2, -1}, {3, 1}  {3, 1, -1}, {3, 0}  {1, 0, 1}} or by using the 6-case s = 2 , k = 4 Turing machine (with initial condition Append[3list, 0] with 0 's on the left and 1 's on the right) {{1, 3}  {2, 2, 1}, {1, 2}  {1, 3, -1}, {1, 1}  {1, 0, -1}, {1, 0}  {1, 1, 1}, {2, 3}  {2, 1, 1}, {2, 0}  {1, 2, 1}} This second Turing machine is directly analogous to the one for rule 110 on page 707 .

RAM [emulated with cellular automata] The rules for the cellular automaton shown here are {{2, 4 | 8, 2 | 11, _, _}  2, {11 | 10, 4 | 8, 2 | 11, _, _}  11, {2, 4 | 8, _, _, _}  10, {11 | 10, 4 | 8, _, _, _}  2, {2, 0, _, _, _}  2, {11, 0, _, _, _}  11, {3 | 7 | 6, _, 10, _, _}  1, {x : (3 | 7 | 6), _, _, _, _}  x, {_, _, 6, 4, 10}  5, {_, _, 6, 8, 10}  9, {_, 3, _, 10, _}  4, {_, 7, _, 10, _}  8, {_, _, 1, _, x : (5 | 9)}  x, {1, _, _, _, _}  1, {_, _, 1, _, _}  1, {_, _, _, _, 1}  1, {_, _, x : (4 | 8 | 0), _, _}  x} The initial conditions are divided into two parts: instructions on the left and memory on the right. Given a list of 0 and 1 values for successive memory locations, the right-hand initial conditions are Flatten[list /. {1  {8, 1}, 0  {4, 1}}] . To access location n the left-hand initial conditions must contain Flatten[{0, i, IntegerDigits[n, 2] /. {1  {0, 11}, 0  {0, 2}}}] inserted in a repetitive {0, 1} background.

Register machines [from cellular automata] Given the program for a register machine in the form used on page 896 , the rules for a cellular automaton that emulates it can be obtained from g[i[1], p_, m_] := {{_, p, _}  p + 1, {_, 0, p}  m + 2, {_, _, p}  m + 3} g[i[2], p_, m_] := {{_, p, _}  p + 1, {p, 0, _}  m + 5, {p, _, _}  m + 6} g[d[1, q_], p_, m_] := {{m + 2 | m + 3, p, _}  q, {m + 1, p, _}  p, {0, p, _}  p + 1, {_, m + 2 | m + 3, p}  m + 1} g[d[2, q_], p_, m_] := {{_, p, m + 5 | m + 6}  q, {_, p, m + 4}  p, {_, p, 0}  p + 1, {p, m + 5 | m + 6, _}  m + 4} RMToCA[prog_] := With[{m = Length[prog]}, Flatten[ {MapIndexed[g[#1, First[#2], m] &, prog], {{0, 0 | m + 1, m + 3}  m + 2, {0, m + 1, _}  0, {0, 0, m + 1}  0, {_, _, x : (m + 1 | m + 3)}  x, {_, m + 1 | m + 3, _}  m + 2, {m + 6, 0 | m + 4, 0}  m + 5, {_, m + 4, 0}  0, {m + 4, 0, 0}  0, {x : (m + 4 | m + 6), _, _}  x, {_, m + 4 | m + 6, _}  m + 5, {_, x_ , _}  x}}]] If m is the length of the register machine program, then the resulting cellular automaton has m + 7 possible colors for each cell. If the initial numbers in the two registers are a and b , then the initial conditions for the cellular automaton are Join[Table[m + 2, {a}], {1}, Table[m + 5,{b}]] surrounded by 0's.