The method based on IntegerDigits in the previous two notes can be improved (notably by power tree methods), but apparently about Log[t] steps are always needed. … But if the list contains a nested sequence, say generated using a substitution system, then about Log[n] steps should be sufficient.

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 .

In the large size limit, the logarithm of this can be approximated by q Log[m/q]/m .

Averaged over all nodes, however, the number of nodes at distance up to r approximates r^Log[2, 3] , implying an effective dimension of Log[2, 3] .

Starting with an ordinary base 2 digit sequence, one prepends a unary specification of its length, then a specification of that length specification, and so on: (Flatten[{Sign[-Range[1 - Length[#], 0]], #}] &)[ Map[Rest, IntegerDigits[Rest[Reverse[NestWhileList[ Floor[Log[2, #] &, n + 1, # > 1 &]]],2]]] (d) Binary-coded base 3. … Flatten[IntegerDigits[ Append[2 - With[{w = Floor[Log[3, 2n]]}, IntegerDigits[n - (3 w + 1 - 1)/2, 3, w]], 3], 2, 2]] (e) Fibonacci encoding. … Apply[Take, RealDigits[(N[#, N[Log[10, #] + 3]] &)[ n √ 5 /GoldenRatio 2 + 1/2], GoldenRatio]] The representations of all the first Fibonacci[n] - 1 numbers can be obtained from (the version in the main text has Rest[RotateLeft[Join[#, {0, 1}]]] & applied) Apply[Join, Map[Last, NestList[{# 〚 2 〛 ], Join[Map[Join[{1, 0}, Rest[#]] & , # 〚 2 〛 ], Map[Join[{1, 0}, #] &, # 〚 1 〛 ]]} &, {{}, {{1}}}, n-3]]]

Ignoring parts that depend on particle masses the result (derived in successive orders from 1, 1, 7, 72, 891 diagrams) is 2 ( 1 + α /(2 π ) + (3 Zeta[3]/4 - 1/2 π 2 Log[2] + π 2 /12 + 197/144) ( α / π ) 2 + (83/72 π 2 Zeta[3] - 215 Zeta[5]/24 - 239 π 4 /2160 + 139 Zeta[3]/18 + 25/18 (24 PolyLog[ 4, 1/2] + Log[2] 4 - π 2 Log[2] 2 ) - 298/9 π 2 Log[2] + 17101 π 2 /810 + 28259/5184) ( α / π ) 3 - 1.4 ( α / π ) 4 + …), or roughly 2. + 0.32 α - 0.067 α 2 + 0.076 α 3 - 0.029 α 4 + … The comparative simplicity of the symbolic forms here (which might get still simpler in terms of suitable generalized polylogarithm functions) may be a hint that methods much more efficient than explicit Feynman diagram evaluation could be used.

Multicolor Turing machines [from 2-color TMs] Given rules in the form on page 888 for a Turing machine with s states and k colors the following yields an equivalent Turing machine with With[{c = Ceiling[Log[2, k]]}, (3 2 c + 2c - 7) s] states (always less than 6.03 k s ) and 2 colors: TMToTM2[rule_, s_, k_] := # /. MapIndexed[ #1  First[#2] &, Union[Map[# 〚 1, 1 〛 &, #]]] &[ With[{b = Ceiling[Log[2, k]] - 1}, Flatten[Table[ {Table[{Table[{{m, i, n, d}, c}  {{m, Mod[i, 2 n - 1 ], n - 1, d}, Quotient[i, 2 n - 1 ], 1}, {n, 2, b}, {i, 0, 2 n - 1}], Table[{ {m, i, 1, d}, c}  {{m, -1, 1, d}, i, d}, {i, 0, 1}], Table[ {{m, -1, n, d}, c}  {{m, -1, n + 1, d}, c, d}, {n, b - 1}], {{m, -1, b, d}, c}  {{0, 0, m}, c, d}}, {d, -1, 1, 2}], Table[{{i, n, m}, c}  {{ i + 2 n c, n + 1, m}, c, -1}, {n, 0, b - 1}, {i, 0, 2 n - 1}], With[{r = 2 b }, Table[ If[i + r c ≥ k, {}, Cases[rule, ({m, i + r c}  {x_, y_, z_})  {{i, b, m}, c}  {{x, Mod[y, r], b, z}, Quotient[y, r], 1})]], {i, 0, r - 1}]]}, {m, s}, {c, 0, 1}]]]] Some of these states are usually unnecessary, and in the main text such states have been pruned. Given an initial condition {i, list, n} the initial condition for the 2-color Turing machine is With[{b = Ceiling[Log[2, k]]}, {i, Flatten[IntegerDigits[list, 2, b]], b n}]

Its boundary has fractal dimension 2 Log[2, Root[2 + # 2 - # 3 , 1]] ≃ 1.52 .

Network (e) effectively has limiting dimension Log[2,3]≃1.58 .

Different current methods asymptotically require slightly different numbers of steps—but all typically at least Exp[Sqrt[Log[n]]] . Nevertheless, to test whether a number is prime ( PrimeQ ) it is known that only a few more than Log[n] steps suffice.