A078612 Number of transitions necessary for a Turing machine to compute the differences between consecutive primes (primes written in unary), when using the instruction table below.

22, 38, 80, 140, 302, 410, 668, 824, 1182, 1832, 2086, 2930, 3572, 3920, 4662, 5892, 7262, 7756, 9320, 10442, 11032, 12884, 14202, 16298, 19310, 20912, 21740, 23438, 24314, 26120, 32900, 34986, 38228, 39350, 45152, 46366, 50092, 53960, 56622, 60732, 64982, 66440

Offset

1,1

Comments

The Turing machine computing this sequence uses the 5-tuple instruction table:

[State, Character, New State, New Character, Direction]

{1,_ 1,_,>} {1,1 1,1,>} {1,- 1,-,>} {1,= 2,_,<} {2,1 3,=,<}

{2,- H,_,<} {3,1 3,1,<} {3,- 4,-,<} {4,_ 4,_,<} {4,1 1,_,>}

(Suzanne Britton), with the read-write head beginning at canonical position.

Links

Table of n, a(n) for n=1..42.

Abelard, On Computable Numbers, with an Application to the Entscheidungsproblem, By A. M. Turing

Michael S. Branicky, Python TM Simulation Code

S. Britton, Turing Machine Simulator [Dead link]

M. Ugarte, Turing Machine Simulator

Formula

a(n) = prime(n+1)-prime(n)+(2*prime(n)+3)*(prime(n)+1) because when started with input string 1^q - 1^p =, with q >= p, the Turing machine halts with 1^(q-p) on its tape after (q-p)+(2*p+3)*(p+1) steps. - Michael S. Branicky, Jul 04 2020

Prog

(Python) # See Branicky link

Crossrefs

Cf. A001223.

Sequence in context: A063252 A078540 A057836 * A039373 A043196 A043976

Adjacent sequences: A078609 A078610 A078611 * A078613 A078614 A078615

Keyword

nonn

Author

Jason Earls, Dec 10 2002

Extensions

Terms beyond a(9) from Michael S. Branicky, Jul 04 2020

Status

approved