Search NKS | Online
21 - 30 of 95 for Log
![](/common/images/search/spacer.gif)
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.
![](/common/images/search/spacer.gif)