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)]] . Large n approximations: (a) n , (b) Log[2, n] , (c) Log[2, n] + Log[2, Log[2,n ]] + … , (d) 2 Log[3, n] , (e) Log[GoldenRatio, n] .

Rule 22—like rule 90 from page 26 —gives a pattern with fractal dimension Log[2,3] ≃ 1.58 ; rule 150 gives one with fractal dimension Log[2, 1+Sqrt[5]] ≃ 1.69 .

Results about primes Prime[n] is given approximately by n Log[n] + n Log[Log[n]] . ( Prime[10 9 ] is 22,801,763,489 while the approximation gives 2.38 × 10 10. ) A first approximation to PrimePi[n] is n/Log[n] . A somewhat better approximation is LogIntegral[n] , equal to Integrate[1/Log[t], {t, 2, n}] . … According to the Riemann Hypothesis, the difference between PrimePi[n] and LogIntegral[n] is of order √ n Log[n] .

Other uniformly distributed sequences Cases in which Mod[a[n], 1] is uniformly distributed include √ n , n Log[n] , Log[Fibonacci[n]] , Log[n!]

Fractal dimensions [of additive cellular automata] The total number of nonzero cells in the first t rows of the pattern generated by the evolution of an additive cellular automaton with k colors and weights w (see page 952 ) from a single initial 1 can be found using g[w_, k_, t_] := Apply[Plus, Sign[NestList[Mod[ ListCorrelate[w, #, {-1, 1}, 0], k] &, {1}, t - 1]], {0, 1}] The fractal dimension of this pattern is then given by the large m limit of Log[k,g[w, k,k m + 1 ]/g[w, k, k m ]] When k is prime it turns out that this can be computed as d[w_, k_:2] := Log[k,Max[Abs[Eigenvalues[With[ {s = Length[w] - 1}, Map[Function[u, Map[Count[u, #] &, #1]], Map[Flatten[Map[Partition[Take[#, k + s - 1], s, 1] &, NestList[Mod[ListConvolve[w, #], k] &, #, k - 1]], 1] &, Map[Flatten[Map[{Table[0, {k - 1}], #} &, Append[#, 0]]] &, #]]] &[Array[IntegerDigits[#, k, s] &, k s - 1]]]]]]] For rule 90 one gets d[{1, 0, 1}] = Log[2, 3] ≃ 1.58 . For rule 150 d[{1, 1, 1}] = Log[2, 1 + √ 5 ] ≃ 1.69 . … For the other rules on page 952 : d[{1, 1, 0, 1, 0}] = Log[2, Root[4 + 2 # - 2 # 2 - 3 # 3 + # 4 &, 2]] ≃ 1.72 d[{1, 1, 0, 1, 1}] = Log[2, Root[-4 + 4 # + # 2 - 4 # 3 + # 4 &, 2]] ≃ 1.80 Other cases include (see page 870 ): d[{1, 0, 1}, k] = 1 + Log[k, (k + 1)/2] d[{1, 1, 1}, 3] = Log[3, 6] ≃ 1.63 d[{1, 1, 1}, 5] = Log[5, 19] ≃ 1.83 d[{1, 1, 1}, 7] = Log[7, Root[-27136 + 23280 # - 7288 # 2 + 1008 # 3 - 59 # 4 + # 5 & , 1]] ≃ 1.85

Instead it is common for a leading digit s in base b to occur with frequency Log[b, (s + 1)/s] (so that in base 10 1's occur 30% of the time and 9's 4.5%). This will happen whenever FractionalPart[Log[b, a[n]]] is uniformly distributed, which, as discussed on page 903 , is known to be true for sequences such as r n (with Log[b, r] irrational), n n , n! , Fibonacci[n] , but not r n , Prime[n] or Log[n] .

The dimensions of the limiting networks are respectively Log[2,3] ≃ 1.58 and Log[3, 7] ≃ 1.77 .

The zeta function as analytically continued for complex s was studied by Bernhard Riemann in 1859, who showed that PrimePi[n] could be approximated (see page 909 ) up to order √ n by LogIntegral[n] - Sum[LogIntegral[n^r[i]], {i, - ∞ , ∞ }] , where the r[i] are the complex zeros of Zeta[s] . The Riemann Hypothesis then states that all r[i] satisfy Re[r[i]]  1/2 , which implies a certain randomness in the distribution of prime numbers, and a bound of order √ n Log[n] on PrimePi[n] - LogIntegral[n] . The Riemann Hypothesis is also equivalent to the statement that a bound of order √ n Log[n] 2 exists on Abs[Log[Apply[LCM, Range[n]]] - n] .

Note that the pattern shown here has been truncated at the edge of the page on the left, although in fact the whole pattern continues to expand to the left forever with an average slope of Log[2, 3]≃1.58 .

Taking into account the length of the representation for each pointer, the compressed form of a nested sequence of length n will typically grow in length like Log[n] 2 . (This can be compared with Log[n] growth for a purely repetitive sequence.)