For any sequence s this can be done using Module[{c, m = 0}, Map[c[#] = {m, m += Count[s, #]/Length[s]} &, Union[s]]; Function[x, (First[RealDigits[2 # Ceiling[2 -# Min[x]], 2, -#, -1]] &)[Floor[Log[2, Max[x] - Min[x]]]]][ Fold[(Max[#1] - Min[#1]) c[#2] + Min[#1] &, {0, 1}, s]]] Huffman coding of a sequence containing a single 0 block together with n 1 blocks will yield output of length about n ; arithmetic coding will yield length about Log[n] .

If the local curvature of the surface is originally c[x, y] , then after such growth, the curvature turns out to be (c[x, y] + Laplacian[Log[h[x, y]]])/h[x, y] where Laplacian[f_] := ∂ xx f + ∂ yy f . In order for the surface to stay flat its growth rate Log[h[x, y]] must therefore solve Laplace's equation, and hence must be a harmonic function Re[f[x +  y]] .

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. … The Batcher method in general requires about n Log[n] 2 comparisons; it is known that in principle n Log[n] are sufficient.

Note that the original rule with k colors and r neighbors involves Log[2, k k 2 r + 1 ] bits of information; the two-color rule that emulates it involves Log[2, 2 2 2 s + 1 ] bits.

Mod[Binomial[t, n], k] is given for prime k by With[{d = Ceiling[Log[k, Max[t, n] + 1]]}, Mod[Apply[Times, Apply[Binomial, Transpose[ {IntegerDigits[t, k, d] , IntegerDigits[n, k, d] }], {1}]], k]] The patterns obtained for any k are nested. For prime k the total number of non-white cells down to step k m is (1/2k (k + 1)) m and the patterns have fractal dimension 1 + Log[k, (k + 1)/2] (see page 955 ).

Digit count sequences Starting say with {1} repeatedly replace list by Join[list, IntegerDigits[Apply[Plus, list], 2]] The resulting sequences grow in length roughly like n Log[n] .

In this case 6 is (1 ∘ (1 ∘ 1)) ∘ 1 , and an integer m can be obtained by Tr[1 + IntegerDigits[m, 2]] - 2 or at most Log[2, m] applications of ∘ . … Note that in all cases the size of the smallest representation must at some level increase like Log[m] (compare pages 1067 and 1070 ), but there may be some "algorithmically simple" integers that have shorter representations.

Note that unlike the case of ordinary additive digits, far more than Log[m] digits are required to specify a number m .

The pattern generated by rule 150R has fractal dimension Log[2, 3 + Sqrt[17]] - 1 or about 1.83.

For large n this number is on average of order Log[n] + 2 EulerGamma - 1 . … For large n , DivisorSigma[1, n] is known to grow at most like Log[Log[n]] n Exp[EulerGamma] , and on average like π 2 /6 n (see page 1093 ). … Hardy and John Littlewood in 1922 to be proportional to 2n Apply[Times, Map[(# - 1)/(# - 2)&, Map[First, Rest[FactorInteger[n]]]]]/Log[n] 2 It was proved in 1937 by Ivan Vinogradov that any large odd integer can be expressed as a sum of three primes.