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. … However, the straightforward method for converting a t -digit number x to base k takes about t divisions, though this can be reduced to around Log[t] by using a recursive method such as FixedPoint[Flatten[Map[If[# < k, #, With[ {e = Ceiling[Log[k, #]/2]}, {Quotient[#, k e ], With[ {s = Mod[#, k e ]}, If[s  0, Table[0, {e}], {Table[0, {e - Floor[Log[k, s]] - 1}], s}]]}]] &, #]] &, {x}] The pictures below show stages in the computation of 3 20 (a) by a power tree in base 2 and (b) by conversion from base 3.

Conway considered fraction systems based on rules of the form FSEvolveList[fracs_, init_, t_] := NestList[First[Select[fracs #, IntegerQ, 1]] &, init, t] With the choice fracs = {17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 95/ 23, 77/19, 1/17, 11/13, 13/11, 15/14, 15/2, 55/1} starting at 2 the result for Log[2, list] is as shown below, where Rest[Log[2, Select[list, IntegerQ[Log[2, #]] &]]] gives exactly the primes.

A major result from the 1980s is that it requires a formula with depth at least Log[n]/(c + Log[Log[n]]) to make it possible to represent an Xor of n variables using a polynomial number of And , Or and Not operations.

The fractal dimension of the (d + 1) -dimensional structure formed from all black cells is Log[2, 1 + 2d] . The 2D analog of rule 150 yields the patterns below; the fractal dimension of the structure in this case is Log[2, (1 + Sqrt[1 + 4/d]) d] .

[Computational complexity of] finding outcomes If one sets up a function to compute the outcome after t steps of evolution from some fixed initial condition—say a single black cell in a cellular automaton—then the input to this function need contain only Log[2, t] digits. But if the evolution is computationally irreducible then to find its outcome will involve explicitly following each of its t steps—thereby effectively finding results for each of the 2^Log[2, t] possible arrangements of digits corresponding to numbers less than t .

But since the 1980s there have been attempts to find general criteria, typically based on maximizing quantities such as -Log[p] - d (the Akaike information criterion), where p is the probability that the observed data would be generated from a given model ( -Log[p] is proportional to variance in a least squares fit), and d is the number of parameters in the model.

The pattern scales differently in the horizontal and vertical direction, corresponding to fractal dimensions Log[2, 5] and Log[4, 5] respectively.

[Intractability in] systems of limited size In the system x  Mod[x + m, n] from page 255 the repetition period n/GCD[m, n] can be computed using Euclid's algorithm in at most about Log[GoldenRatio, n] steps. In the system x  Mod[2x, n] from page 257 , the repetition period MultiplicativeOrder[2, n] probably cannot always be computed in any polynomial of Log[n] steps, since otherwise FactorInteger[n] could also be computed in about this number of steps. … With sufficiently simple behavior, a cellular automaton repetition period can readily be determined in some power of Log[n] steps.

Note the inequality 1 ≤ DigitCount[n, 2, 1] ≤ Log[2, n] . … , 2] and 2n - Log[2, Denominator[Derivative[n][(1 - #) -1/2 &][0]/n!]]

As an example, the n th digit of Log[2] in base 2 is formally given by Round[FractionalPart[2 n Sum[2 -k /k, {k, ∞ }]]] . … The same basic approach as for Log[2] can be used to obtain base 16 digits in π from the following formula for π : Sum[16 -k (4/(8k + 1) - 2/(8k + 4) - 1/(8k + 5)-1/(8k + 6)), {k, 0, ∞ }] A similar approach can also be used for many other constants that can be viewed as related to values of PolyLog .