Since numbers can be factored uniquely into products of powers of primes, a number can be specified by a list in which 1's appear at the positions of the appropriate Prime[m] n (which can be sorted by size) and 0's appear elsewhere, as shown below. Note that unlike the case of ordinary additive digits, far more than Log[m] digits are required to specify a number m .

These numbers can also be obtained as the coefficients of x n in the series expansion of x ∂ x Log[ ζ [m, x]] , with the so-called zeta function, which is always a rational function of x , given by ζ [m_, x_] := 1/Det[IdentityMatrix[Length[m]] - m x] and corresponds to the product over all cycles of 1/(1 - x n ) .

The element at position n in the first sequence discussed above can however be obtained in about Log[n] steps using ((IntegerDigits[#3 + Quotient[#1, #2], 2] 〚 Mod[#1, #2] + 1 〛 &)[n - (# - 2)2 # - 1 - 2, #, 2 # - 1 ]&)[NestWhile[# + 1&, 0, (# - 1)2 # + 1 < n &]] where the result of the NestWhile can be expressed as Ceiling[1 + ProductLog[1/2(n - 1)Log[2]]/Log[2]] Following work by Maxim Rytin in the late 1990s about k n+1 digits of a concatenation sequence can be found fairly efficiently from k/(k - 1) 2 - (k - 1) Sum[k (k s - 1) ((1 + s - s k)/(k - 1)) (1/((k - 1) (k s - 1) 2 ) - k/((k - 1) (k s + 1 - 1) 2 ) + 1/(k s + 1 - 1)), {s, n}] Concatenation sequences can also be generated by joining together digits from other representations of numbers; the picture below shows results for the Gray code representation from page 901 .

Zeta function For real s the Riemann zeta function Zeta[s] is given by Sum[1/n s , {n, ∞ }] or Product[1/(1 - Prime[n] s ), {n, ∞ }] . … 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] .

Given two numbers x and y their product can be computed in base k by ( FromDigits does the carries) FromDigits[ListConvolve[IntegerDigits[x, k], IntegerDigits[y, k], {1, -1}, 0], k] For numbers with n digits direct evaluation of the convolution would take about n 2 steps. But FFT-related methods reduce this to about n Log[n] steps (see also page 1142 ). And this implies that to find a particular digit of m t in base k will take altogether about t Log[t] 2 steps.

The encoded version of a purely repetitive sequence of length n has a length that grows like Log[n] . The encoded version of a purely nested sequence grows like Log[n] 2 . … An example is the sequence Table[Append[Table[0, {r}], 1], {r, s}] whose encoded version grows like √ n Log[n] .

Most arose first as solutions to specific differential equations, typically in physics and astronomy; some arose as products, sums of series or inverses of other functions. In the mid-1800s it became clear that despite their different origins most of these functions could be viewed as special cases of Hypergeometric2F1[a, b, c, z] , and that the functions covered the solutions to all linear differential equations of a certain type. ( Zeta and PolyLog are parametric derivatives of Hypergeometric2F1 ; elliptic modular functions are inverses.) … (Typically one needs to generalize formulas that are initially set up with integer numbers of terms; examples include taking Power[x, y] to be Exp[Log[x] y] and x!

It exhibits a nested structure, and can be obtained as in the pictures below from the evolution of a 2D substitution system, or equivalently from a Kronecker product as in Nest[Flatten2D[Map[# {{1, 1}, {1, -1}} &, #, {2}]] &, {{1}}, s] with Flatten2D[a_] := Apply[Join, Apply[Join, Map[Transpose,a], {2}]] (c) is known as dyadic or Paley order. It is related to (a) by Gray code reordering of the rows, and to (b) by reordering according to (see page 905 ) BitReverseOrder[a_] := With[{n = Length[a]}, a 〚 Map[FromDigits[Reverse[#], 2] &, IntegerDigits[Range[0, n - 1], 2, Log[2, n]]] + 1 〛 ] It is also given by Array[Apply[Times, (-1)^(IntegerDigits[#1, 2, s] Reverse[IntegerDigits[#2, 2, s]])] &, 2^{s,s}, 0] where (b) is obtained simply by dropping the Reverse . … However, the nested structure of m in natural order allows evaluation in only about n Log[n] steps using Nest[Flatten[Transpose[Partition[#, 2] . {{1, 1}, {1, -1}}]] &, data, Log[2, Length[data]]] This procedure is similar to the fast Fourier transform discussed below.

After a large number of steps t , the number of distinct positions visited will be proportional to t , at least above 2 dimensions (in 2D, it is proportional to t/Log[t] and in 1D √ t ). Note that the outer boundaries of patterns like those on page 330 formed by n random walks tend to become rougher when t is much larger than Log[n] . … As discussed in the note below, this can be viewed as a consequence of the fact that the probability distribution in a random walk depends only on Sum[Outer[Times, e 〚 s 〛 , e 〚 s 〛 ], {s, Length[e]}] and not on products of more of the e 〚 s 〛 .

The first 2 m elements in the sequence can be obtained from (see page 1081 ) (CoefficientList[Product[1 - z 2 s , {s, 0, m - 1}], z] + 1)/2 The first n elements can also be obtained from (see page 1092 ) Mod[CoefficientList[Series[(1 + Sqrt[(1 - 3x)/(1 + x)])/ (2(1 + x)), {x, 0, n - 1}], x], 2] The sequence occurs many times in this book; it can for example be derived from a column of values in the rule 150 cellular automaton pattern discussed on page 885 . … The resulting curve has a nested form, with envelope n^Log[3, 2] .