# Turing Machine Simulator
# MS Branicky, Dec 14 2019, Jul 03-05 2020

# https://oeis.org/A078612

# The Turing machine computing this sequence uses the 5-tuple instruction table:
# (State, Character) : (New State, New Character, Direction)

transition_table = {
  ('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', '_', '>'),
}

# start, accept, and reject states
start  = '1'
halt = 'H'
BLANK = '_'

def simulate(p,q):
    # input string
    input_string = ("1"*p)+"-"+("1"*q)+"="

    # instantaneous description (id) at start
    state = start
    head_position = 0
    tape = list(input_string)

    # simulate the machine
    steps = 0
    while state!=halt and head_position>=0:
        state, symbol_to_write, direction_to_move = transition_table[state, tape[head_position]]
        tape[head_position] = symbol_to_write
        if direction_to_move == '>':
            head_position += 1
            if head_position==len(tape):
                tape.append(BLANK)
        elif direction_to_move=='<':
            head_position -= 1
        #print_id( (state, head_position, tape) )
        steps += 1
        if state==halt:
            return steps

from sympy import sieve

N = 43
sieve.extend_to_no(N)

ans = []
for n in range(1,N):
    p, q = sieve[n], sieve[n+1]
    steps_sim = simulate(q, p)
    steps_formula = p+q+1 + (2*p+3)*p + 2
    steps_formula2 = (2*p+3)*(p+1) + (q-p)
    print(f"a({n}) = {steps_sim} = {steps_formula2}")
    assert steps_sim==steps_formula
    ans.append(steps_sim)
print()
print(len(str(ans)), ans)


"""
// program for https://turingmachinesimulator.com/

init: 1
accept: H

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,_,>
"""