Implementation of digit sequences A whole number n can be converted to a sequence of digits in base k using IntegerDigits[n,k] or (see also page 1094 ) Reverse[Mod[NestWhileList[Floor[#/k] &, n, # ≥ k &], k]] and from a sequence of digits using FromDigits[list,k] or Fold[k #1 + #2 &, 0, list] For a number x between 0 and 1, the first m digits in its digit sequence in base k are given by RealDigits[x, k, m] or Floor[k NestList[Mod[k #, 1]&, x, m - 1]] and from these digits one can reconstruct an approximation to the number using FromDigits[{list, 0}, k] or Fold[#1/k + #2 &, 0, Reverse[list]]/k

[Spectra of] random block sequences Analytical forms for all but the last spectrum are: 1 , u 2 /(1 + 8u 2 ) , 1/(1 + 8 u 2 ) , u 2 , (1 - 4u 2 ) 2 /(1 - 5u 2 + 8u 4 ) , u 2 /(1 - 5u 2 + 8u 4 ) , u 2 + 1/36 DiracDelta[ ω - 1/3] , where u = Cos[ π ω ] , and ω runs from 0 to 1/2 in each plot. Given a list of blocks such as {{1, 1}, {0}} each element of Flatten[list] can be thought of as a state in a finite automaton or a Markov process (see page 1084 ). … If ξ [r] = λ r then the spectrum is (1 - λ 2 )/( λ 2 - 2 λ Cos[2 π ω ] + 1) - 1 .

Properties of [recursive] sequences Sequence (d) is given by f[n_] := (n + g[IntegerDigits[n, 2]])/2 g[{1 ..}] = 1; g[{1, 0 ..}] = 0 g[{1, s__}] := 1 + g[IntegerDigits[FromDigits[{s}, 2] + 1, 2]] The list of elements in the sequence up to value m is given by Flatten[Table[Table[n, {IntegerExponent[n, 2] + 1}], {n, m}]] The differences between the first 2 (2 k -1) of these elements is Nest[Replace[#, {x___}  {x, 1, x, 0}]&, {}, k] The largest n for which f[n]  m is given by 2m + 1 - DigitCount[m, 2, 1] or IntegerExponent[(2m)!, 2] + 1 (this satisfies h[1] = 2; h[m_] := h[Floor[m/2]] + m ). … Hump m in the picture of sequence (c) shown is given by FoldList[Plus, 0, Flatten[Nest[Delete[NestList[Rest, #, Length[#] - 1], 2]&, Append[Table[1, {m}], 0], m]] - 1/2] The first 2 m elements in the sequence can also be generated in terms of reordered base 2 digit sequences by FoldList[Plus, 1, Map[Last[Last[#]]&, Sort[Table[{Length[#], Apply[Plus, #], 1 - #}& [ IntegerDigits[i, 2]], {i, 2 m }]]]] Note that the positive and negative fluctuations in sequence (f) are not completely random: although the probability for individual fluctuations in each direction seems to be the same, the probability for two positive fluctuations in a row is smaller than for two negative fluctuations in a row.

Nand theorems The total number of expressions with n Nand s and s variables is: Binomial[2n, n]s n + 1 /(n + 1) (see page 897 ). With s = 2 and n from 0 to 7 the number of these True for all values of variables is {0, 0, 4, 0, 80, 108, 2592, 7296} , with the first few distinct ones being (see page 781 ) {(p ⊼ p) ⊼ p, (((p ⊼ p) ⊼ p) ⊼ p) ⊼ p, (((p ⊼ p) ⊼ p) ⊼ q) ⊼ q} The number of unequal expressions obtained is {2, 3, 3, 7, 10, 15, 12, 16} (compare page 1096 ), with the first few distinct ones being {p, p ⊼ p, p ⊼ q, (p ⊼ p) ⊼ p, (p ⊼ q) ⊼ p, (p ⊼ p) ⊼ q} Most of the axioms from page 808 are too long to appear early in the list of theorems.

Implementation [of conserved quantity test] Whether a k -color cellular automaton with range r conserves total cell value can be determined from Catch[Do[ (If[Apply[Plus, CAStep[rule, #] - #] ≠ 0, Throw[False]] &)[ IntegerDigits[i, k, m]], {m, w}, {i, 0, k m - 1}]; True] where w can be taken to be k 2r , and perhaps smaller. … Among the 2 32 k = 2 , r = 2 rules 428 do, and of these 2 are symmetric, and 6 are reversible, and all these are just shift and identity rules.

1D [discrete] transitions [in cellular automata] There are no examples of the phenomenon shown here among the 256 rules with two possible colors and depending only on nearest neighbors. … An example that depends on three neighbors on each side was discovered by Peter Gacs , Georgii Kurdyumov and Leonid Levin in 1978, following work on how reliable electronic circuits can be built from unreliable components by Andrei Toom : {a1_, a2_, a3_, a4_, a5_, a6_, a7_}  If[If[a4  1, a1 + a3 + a4, a4 + a5 + a7] ≥ 2, 1, 0] The 4-color rule shown in the text is probably the clearest example available in one dimension.

Negative bases Given a suitable list of digits from 0 to k - 1 one can obtain any positive or negative number using FromDigits[list, -k] . The picture below shows the digit sequences of successive numbers in base -2; the row j from the bottom turns out to consist of alternating black and white blocks of length 2 j . (In ordinary base 2 a number -n can be represented as on a typical electronic computer by complementing each digit, including leading 0's.)

Historically, the number of decimal digits of π that have been computed is roughly as follows: 2000 BC (Babylonians, Egyptians): 2 digits; 200 BC ( Archimedes ): 5 digits; 1430 AD: 14 digits; 1610: 35 digits; 1706: 100 digits; 1844: 200 digits; 1855: 500 digits; 1949 (ENIAC computer): 2037 digits; 1961: 100,000 digits (IBM 7090); 1973: 1 million; 1983: 16 million; 1989: 1 billion; 1997: 50 billion; 1999: 206 billion. In the first 200 billion digits, the frequencies of 0 through 9 differ from 20 billion by {30841, -85289, 136978, 69393, -78309, -82947, -118485, -32406, 291044, -130820} An early approximation to π was 4 Sum[(-1) k /(2k + 1), {k, 0, m}] 30 digits were obtained with 2 Apply[Times, 2/Rest[NestList[Sqrt[2 + #]&, 0, m]]] An efficient way to compute π to n digits of precision is (# 〚 2 〛 2 /# 〚 3 〛 )& [NestWhile[Apply[Function[{a, b, c, d}, {(a + b)/2, Sqrt[a b], c - d (a - b) 2 , 2 d}], #]&, {1, 1/Sqrt[N[2, n]], 1/4, 1/4}, # 〚 2 〛 ≠ # 〚 2 〛 &]] This requires about Log[2, n] steps, or a total of roughly n Log[n] 2 operations (see page 1134 ).

But since every value must be either 0 or 1, it can in fact be encoded by just a single bit. … And thus for example the values of all cells represented by an integer variable a can be updated in parallel according to rule 30 by the single C statement a = a > > 1 ^ (a | a < < 1); This statement, however, will only update the specific block of cells encoded in a . … The idea is to store the cellular automaton configuration in, say, m variables w[i] whose bits correspond respectively to the cell values {a 1 , a m + 1 , a 2m + 1 , …} , {a 2 , a m + 2 , a 2m + 2 , …} , {a 3 , …} , etc.

The first one on the bottom (with 63 comparisons) has a nested structure and uses the method invented by Kenneth Batcher in 1964: Flatten[Reverse[Flatten[With[{m = Ceiling[Log[2, n]] - 1}, Table[With[{d = If[i  m, 2 t , 2 i + 1 - 2 t ]}, Map[ {0, d} + # &, Select[Range[n - d], BitAnd[# - 1, 2 t ]  If[i  m, 0, 2 t ] &]]], {t, 0, m}, {i, t, m}]], 1]], 1] The second one on the bottom also uses 63 comparisons, while the last one is the smallest known for n = 16 : it uses 60 comparisons and was invented by Milton Green in 1969. For n ≤ 16 the smallest numbers of comparisons known to work are {0, 1, 3, 5, 9, 12, 16, 19, 25, 29, 35, 39, 45, 51, 56, 60} . (In general all lists will be sorted correctly if lists of just 0's and 1's are sorted correctly; allowing even just one of these 2 n cases to be wrong greatly reduces the number of comparisons needed.)