|
|
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.
|
|
1
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|