[Turing] machine 600720
(Case (h) of page 763.) The maximum halting times for the first few sizes n are
{5, 159, 161, 1021, 5419, 315391, 1978213883, 1978213885, 3018415453261}
These occur for inputs {1, 2, 5, 10, 26, 34, 106, 213, 426} and correspond to outputs (each themselves maximal for given n)
2^{3, 23, 24, 63, 148, 1148, 91148, 91149, 3560523} - 1
Such maxima often seem to occur when the input x has the form (20 4s - 2)/3 (and so has digits {1, 1, 0, 1, 0, …, 1, 0}). The output f[x] in such cases is always 2u - 1 where
u = Nest[(13 + (6# + 8)(5/2)^IntegerExponent[6# + 8, 2])/6 &, 1, s + 1]
One then finds that 6u + 8 has the form Nest[If[EvenQ[#], 5#/2, # + 21]&, 14, m] for some m, suggesting a connection with the number theory systems of page 122. The corresponding halting time t[x] is Last[Nest[h, {8, 4s + 24 }, s]] - 1 with
h[{i_, j_}] := With[{e = IntegerExponent[3i + 4, 2]}, {13/6 + (i + 4/3)(5/2)e + 1, ((154 + 75(i + 4/3)(5/2)e)2 - 16321 - 7860i - 900i2 + 3360e)/3780 + j}]
For s > 3 it then turns out that f[x] is extremely close to 3560523 (5/2)r, and t[x] to 18865098979373 (5/2)2r, for some integer r.
It is very difficult in general to find traditional formulas for f[x] and t[x]. But if IntegerDigits[x, 2] involves no consecutive 0's then for example f[x] can be obtained from
2^(b[Join[{1, 1}, #], Length[#]] &)[IntegerDigits[x, 2]] - 1
a[{l_, _}, r_] := ({l + (5r - 3#)/2, #} &)[Mod[r, 2]]
a[{l_, 0}, 0] := {l + 1, 0}
a[{l_, 1}, 0] := ({(13 + #(5/2)^IntegerExponent[#, 2])/6, 0} &[6l + 2]
b[list_, i_] := First[Fold[a, {Apply[Plus, Drop[list, -i]], 0}, Apply[Plus, Split[Take[list, -i], #1 #2 ≠ 0 &], 1]]]
(The corresponding expression for t[x] is more complicated.) A few special cases are:
f[4s] = 4s + 3
f[4s + 1] = 2f[2s] + 1
f[2s - 1] = 2(10s + 5 + 3 (-1)s)/4 - 1
How the halting times behave for large n is not clear. It is certainly possible that they could increase like NestList[#2 &, 2, n], or 22n, although for x = (20 4s - 2)/3 a better fit for n≤200 is just 22.6 n, with outputs increasing like 221.3 n.