A393106 Halting time for Wolfram's 2-state 2-symbol Turing machine 261 when started with n on the tape.

5, 7, 7, 3, 9, 9, 9, 3, 5, 11, 11, 3, 11, 11, 11, 3, 5, 7, 7, 3, 13, 13, 13, 3, 5, 13, 13, 3, 13, 13, 13, 3, 5, 7, 7, 3, 9, 9, 9, 3, 5, 15, 15, 3, 15, 15, 15, 3, 5, 7, 7, 3, 15, 15, 15, 3, 5, 15, 15, 3, 15, 15, 15, 3, 5, 7, 7, 3, 9, 9, 9, 3, 5, 11, 11, 3, 11

Offset

1,1

Comments

See A392245 for further details.

All terms are odd since position -1 can be reached from position 0 only with an odd number of +-1 steps. (This holds obviously for any 1-dimensional movement.) - M. F. Hasler, Feb 08 2026

Links

Sean A. Irvine, Table of n, a(n) for n = 1..1000

Michael S. Branicky, Python programs for Wolfram's 2-state 2-symbol TMs 1285, 3333 and 261.

Stephen Wolfram, P vs. NP and the Difficulty of Computation: A Ruliological Approach, 2026.

Wolfram Research, The Wolfram Atlas of Simple Programs: Machine 261.

Formula

a(n) = 3 iff n = 0 (mod 4); a(n) = 5 iff n = 1 (mod 8); a(n) = 7 iff n = 2 or 3 (mod 16); a(n) = 9 iff n = 5, 6 or 7 (mod 32); a(n) = 11 iff n = 10, 11, 13, 14 or 15 (mod 64), etc. - M. F. Hasler, Feb 08 2026

Mathematica

With[{lim = 74}, PacletSymbol["WolframInstitute/TuringMachine", "OneSidedTuringMachineFunction"][{261, 2, 2}, {1, lim}, lim, "Steps"] ] (* Michael De Vlieger, Feb 06 2026, modified from 5th example in "The Basic Setup" in "P vs. NP ..." *)

Prog

(Python) # see linked program
(PARI) A393106(n)=A393103(n, 261); \\ Cf. A393103 for the function; this uses just a different rule. - M. F. Hasler, Feb 08 2026

Crossrefs

Cf. A392245 (result computed by this TM for input n), A393103 (halting time for rule 1285), A393146 (halting time for rule 3333).

Sequence in context: A210623 A020760 A225155 * A011269 A093723 A065773

Adjacent sequences: A393103 A393104 A393105 * A393107 A393108 A393109

Keyword

nonn

Author

Sean A. Irvine, Feb 01 2026

Status

approved