A389270 Number computed by Wolfram's 3-state 2-symbol Turing machine 1342057 when started with n on the tape.

0, 7, 2, 7, 4, 3, 6, 11, 8, 15, 10, 15, 12, 15, 14, 19, 16, 23, 18, 23, 20, 19, 22, 27, 24, 31, 26, 31, 28, 31, 30, 35, 32, 39, 34, 39, 36, 35, 38, 43, 40, 47, 42, 47, 44, 47, 46, 51, 48, 55, 50, 55, 52, 51, 54, 59, 56, 63, 58, 63, 60, 63, 62, 67, 64, 71, 66

Offset

1,2

Comments

Machine 1342057 computes this function with asymptotic runtime 4^n, but there exists a 4-state 2-symbol machine (number 1517414255) which computes this function with worst-case runtime of 7.

Links

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

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

Mathematica

With[{lim = 67, len = 2^20}, PacletSymbol["WolframInstitute/TuringMachine", "OneSidedTuringMachineFunction"][{1342057, 3, 2}, {1, lim}, len]] (* Michael De Vlieger, Feb 22 2026 *)

Crossrefs

Cf. A393542, A392245.

Sequence in context: A328904 A352301 A177437 * A242021 A096052 A003677

Adjacent sequences: A389267 A389268 A389269 * A389271 A389272 A389273

Keyword

nonn

Author

Sean A. Irvine, Feb 22 2026

Status

approved