In general, the dot will visit position m = k^IntegerExponent[n, k] every MultiplicativeOrder[k, n/m] steps.

[No text on this page] Universality in arithmetic, illustrated by an integer equation whose solutions in effect emulate the rule 110 universal cellular automaton from Chapter 11 . … Note that the equation shown is a so-called exponential Diophantine one, in which some variables appear in exponents.

This is nonzero when all prime factors of n of the form 4k + 3 appear with even exponents. … Note that the total number of integers less than n which can be expressed as a sum of three squares increases roughly like 5n/6 , with fluctuations related to IntegerDigits[n, 4] . … The total number of ways that integers less than n can be expressed as a sum of d squares is equal to the number of integer lattice points that lie inside a sphere of radius Sqrt[n] in d -dimensional space.

For all initial conditions this depth seems at first to increase linearly, then to decrease in a nested way according to FoldList[Plus, 0, Flatten[Table[ {1, 1, Table[-1, {IntegerExponent[i, 2] + 1}]}, {i, m}]]] This quantity alternates between value 1 at position 2 j and value j at position 2 j - j + 1 .

An alternative formulation is to ask whether for all n FixedPoint[(3#/2^IntegerExponent[#, 2] + 1)/2 &, n]  2 With the rule n  If[EvenQ[n], 5n/2, (n + 1)/2] used in the main text, the sequence produced repeats if n ever reaches 2, 4 or 40 (and possibly higher numbers). … Starting with n = 6 , the effective exponents for t = 10^Range[6] are {39.6, 245.1, 1202.8, 9250.7, 98269.8, 1002020.4} .

And the reason is that one can generate the elements in it by effectively maintaining a copy of the Turing machine for each possible initial condition, then following a procedure where for example at step n one updates the one for initial condition IntegerExponent[n, 2] , and watches to see if it halts.

The n th element is given by Mod[IntegerExponent[n, 2], 2] .

So for example the equation a 2 + b 2  0 has solutions that are exactly those integers that satisfy the relation a  0 ∧ b  0 . … In the universal equation in the main text variables appear in exponents. One can reduce such an exponential equation to a pure polynomial equation by encoding powers using integer equations.

The number of steps before a machine with given rule halts can be computed from (see page 888 ) Module[{s = 1, a, i = 1, d}, a[_] = 0; MapIndexed[a[#2 〚 1 〛 ] = #1 &, Reverse[IntegerDigits[x, 2]]]; Do[{s, a[i], d} = {s, a[i]} /. rule; i -= d; If[i  0, Return[t]], {t, tmax}]] Of the 4096 Turing machines with s = 2 , k = 2 , 748 never halt, 3348 sometimes halt and 1683 always halt. … Machine 1447 (example (e)) computes the function which takes the digit sequence of x and replaces its first 3 + IntegerExponent[x + 1, 2] 0's by 1's.

(d) (Period-doubling sequence) The spectrum is (2 # - (-1) # &)[1 + IntegerExponent[n, 2]] , almost like the markings on a base 2 ruler.