Reverse busy beaver problem In this challenge, Turing machines operate on a zero-initialized binary tape that is infinite in both directions.
You are given an integer \$N\$, where \$1 \le N \le 20000\$. Your program has to output a Turing machine that takes exactly \$N\$ steps to halt, including the final step. Alternatively, you can write a program that outputs all 20000 machines.
Your program should complete within 2 hours for all 20000 inputs, when tested on my computer (AMD Ryzen 2600 12-thread CPU). If your program solves all test cases on the same thread, sequentially and independently, your program's running time is divided by 4.
Your score is the total number of states in all 20000 outputs of your program. The lowest-scoring program wins.
Output
Below is described the (recommended) output format for a single test case.
In the first line, output a number \$M\$, the number of states of the machine. In the next \$M\$ lines, output the transitions from the states, in order from the first to the last, if the cell under the pointer is zero. In the next \$M\$ lines, output the corresponding transitions, if the cell under the pointer is one.
The output format for transitions is movement newval newstate, where movement stands for either L - move left, R - move right, S - do not move, or H - halt, newval is the new value of the cell under the pointer (it can be equal to the original one), and newstate is an integer from \$1\$ to \$M\$, the state the machine will be in in the next step.
Python 3 checker that inputs in the format described above and outputs the number of steps the Turing machine takes to halt. If you use a different output format, please include a link to a program that can  be used to simulate your Turing machines (it's likely a good idea to simply modify my checker).
Python 3, 275,467 255,540 states
Thanks @mypronounismonicareinstate for suggesting to add \$I\$ into the \$B \rightarrow C\$ loop, which ultimately saves about \$20k\$ states.

def print_machine(states):
 print(len(states[0]))
 for i in 0,1:
  for s in states[i]:
   # if s is None (state unused), puts dummy value in there
   move, new_val, new_state = s or ["H", 0, 0]
   print(move, new_val, new_state+1)

# simple machine that uses ceil(step/2) states
# used for small cases
def generate_simple_machine(steps):
 n_states = (steps+1)//2
 # states[cur_char][state_id]
 states = [[], []]
 for i in range(n_states):
  states[0].append(["S", 1, i])
  states[1].append(["S", 0, i+1])
 states[1][-1][0] = "H"
 if steps%2==1: states[0][-1][0] = "H"
 return states


BASE_STEPS = [(1&lt;&lt;i+2)-i-3 for i in range(20)]
BASE_STEPS[0] = -999

def generate_counter_machine(steps, do_print=True):
 # how many bits/states needed?
 for n_bits, max_steps in enumerate(BASE_STEPS):
  if max_steps &gt; steps:
   break
 n_bits -= 1
 n_states = n_bits + 2
 extra = steps - BASE_STEPS[n_bits]
 if extra &gt;= (1 &lt;&lt; (n_bits+1)):
  n_states += 1
&#32;
 # if small number of steps, use simple machine
 n_states_simple = (steps+1)//2
 if not do_print:
  return min(n_states_simple, n_states)
 if n_states &gt;= n_states_simple :
  states = generate_simple_machine(steps)
  print_machine(states)
  return n_states_simple

 # states[cur_char][state_id]
 # use 0 indexed state
 states = [[None]*n_states, [None]*n_states]

 # state indices
 I_STATE  = 0
 B_STATE  = 1
 E_STATE  = n_states - 1
 C_STATES = [i+2 for i in range(n_bits)]

 # initial state
 states[0][I_STATE] = ["R", 1, C_STATES[0]]
 states[1][I_STATE] = ["H", 0, 0]  # not used initially

 # go back state
 states[0][B_STATE] = ["L", 0, B_STATE]
 states[1][B_STATE] = ["R", 1, C_STATES[0]]

 # ith-digit check states
 for i in C_STATES:
  states[0][i] = ["L", 1, B_STATE]
  states[1][i] = ["R", 0, i+1]
 states[1][C_STATES[-1]][0] = "H"

 # dealing with extras
 # first, figure out how many half-state
 # goes between B_1 -&gt; C1_x
 t = 1&lt;&lt;n_bits
 q1 = t - 1
 q2 = q1 + t
 q3 = q2 + t
 if  extra &lt; q1:
  extra_state = I_STATE
 elif extra &lt; q2:
  # connect B_1 -&gt; I_0 -&gt; C1_?
  states[1][B_STATE] = ["S", 0, I_STATE]
  extra -= q1
  extra_state = I_STATE
 elif extra &lt; q3:
  # connect B_1 -&gt; I_0 -&gt; I_1 -&gt; C1_x
  states[1][B_STATE] = ["S", 0, I_STATE]
  states[0][I_STATE] = ["S", 1, I_STATE]
  states[1][I_STATE] = ["R", 1, C_STATES[0]]
  extra -= q2
  extra_state = E_STATE
 else:
  # connect B_1 -&gt; I_0 -&gt; I_1 -&gt; E_0 -&gt; C1_x
  states[1][B_STATE] = ["S", 0, I_STATE]
  states[0][I_STATE] = ["S", 1, I_STATE]
  states[1][I_STATE] = ["S", 0, E_STATE]
  states[0][E_STATE] = ["R", 1, C_STATES[0]]
  extra -= q3
  extra_state = E_STATE

 # then put a half-state between Cx_0 -&gt; B
 # if needed
 if extra &gt; 0:
  states[1][extra_state] = ["L", 1, B_STATE]&#32;
  for i in reversed(C_STATES):
   if extra%2==1:
    states[0][i] = ["S", 1, extra_state]
   extra //= 2
 print_machine(states)
 return n_states

Try it online! or Verify all machines from 1 to 20k
Big idea
We want to construct a Turing machine that has a large time complexity compared to the number of states. In this answer, I used a binary counter to count all integers with \$n\$ bits, which has a time complexity of \$O(2^n)\$. The binary counter was chosen because it is very simple to construct, easy to scale, and flexible enough to add any small number of steps.
Binary counter
Let's say we want to count all integers with 4 bits. The tape layout will be as follows:
1 x x x x
e.g.
1 0 0 0 0
1 1 0 0 0
....
1 0 1 1 1
1 1 1 1 1

where the left most 1 is used to mark the start of the number, and xxxx is the current number in binary, in reverse order (the least significant bit first). We start with 10000, and end with 11111.
At each cycle, we increase the number by 1 as follows:

Find the left most 0. E.g.

1 1 1 0 1
      ^


Set that digit to 1, and all previous digits to 0. The previous example becomes 1 0 0 1 1.

We then repeat these steps until the tape is 1 1 1 1 1.
Binary counter Turing machine
The counter machine for \$b\$-bit integers will have \$b+2\$ states: the initial state \$I\$, \$b\$ digit check states \$C_1\$ to \$C_b\$, and the &quot;go back&quot; state \$B\$:

The initial state \$I\$ simply sets the left most cell to 1: R 1 C1 / x x x.

The \$i^{th}\$ digit check state \$C_i\$ is only called if all previous digits are 1, and the pointer is currently on the \$i^{th}\$ left most digit.

If the current digit is 0, then we've found the left most 0. Set the current digit to 1, and enter &quot;go back&quot; state: L 1 B.
If the current digit is 1, set that digit to 0 and enter the next digit check state: R 0 C(i+1). If this is the last digit check state (\$C_b\$), then halts, since this means the current number is 111..1.


&quot;Go back&quot; state \$B\$ is called after the number is incremented, to reset the pointer to the unit digit and start a new cycle. This state simply moves left until it sees the 1 that marks the start of the number. It then moves one step right to the unit digit, and calls the first digit check state \$C_1\$: L 0 B / R 1 C1.



Time complexity
With \$n\$ states (counting \$n-2\$ bit integers), a counter machine runs for \$2^n-n-1\$ steps.
states  steps
     3      4
     4     11
     5     26
     6     57
     7    120
     8    247
     9    502
    10   1013
    11   2036
    12   4083
    13   8178
    14  16369
    15  32752

Bridging the gap
The above scheme only allows us to generate machines with the exact number of steps in the table above. This means that we are stuck if the number of steps falls in the &quot;gaps&quot; between the above numbers. Thankfully, there is a simple scheme that allow us to add some extra steps to a machine, at the cost of at most 1 state.
For example, from the above table, we know that a counter with 6 states runs for 57 steps, and a machine with 7 states runs for 120 steps. There are 62 numbers in the gap between them (58 to 119). This means that we need to be able to extend a 6-state machine to have 1 to 62 extra steps. (In general, we need a scheme to extend an \$n\$-states machine by 1 to \$2^n-2\$ steps).
First, some notation: let's \$S^0\$ and \$S^1\$ be the &quot;half-states&quot; of \$S\$, aka \$S\$ when the current cell is 0 or 1.
Let's look at how many time each half-state is called in an original 6-state counter machine:
                I    B   C1   C2   C3   C4
cur_char = 0    1   11    8    4    2    1
cur_char = 1    0   15    8    4    2    1

Observation 1
The number of times each digit check half-state is called is always a power of 2. Furthermore, the transition afterward is always \$C_i^0 \rightarrow B^x\$ (refer to the state transition diagram above). This means that we can add an extra half-state in between (aka \$C_i^0 \rightarrow X \rightarrow B^x\$). The extra half-state simply wastes a step before transitioning to \$B\$. The number of extra steps gained is equal to the number of times \$C_i^0\$ is called.
By selecting which \$C_i^0\$ are connected to this extra half-state \$X\$, we can add any number of extra steps from 1 to 15 (since \$15=8+4+2+1\$), at the cost of 1 extra half-state.

For example, in the modified counter above, \$C_1^0\$ and \$C_3^0\$ transitions through \$X\$ before reaching \$B\$. Since \$C_1^0\$ is called 8 times and \$C_3^0\$ is called 2 times, \$X\$ is called 10 times in total, adding an extra 10 steps to the machine.
Observation 2:
Both \$B^1\$ and \$I^0\$ transitions to state \$C_1\$. Furthermore, both \$B^1\$ and \$I^0\$ sets the current cell to 1, then moves right. Thus, we can have \$B^1 \rightarrow I^0 \rightarrow C_1^x\$. This gives us an extra 15 steps for free.
Furthermore, for each additional half-state inserted between \$I^0\$ and \$C_1^x\$, the machine runs for 16 extra steps. For example, using 2 extra half-state, we can gain \$15+16+16=47\$ extra steps.
By combining the 2 observations, we can reach any number of extra steps between 1 and 62 inclusive, using at most 3 extra half-states (1 half-state in observation 1, 2 in observation 2, which gives at most \$15 + 47 = 62\$ extra steps).

For example, in the machine above, \$I^0\$ and 2 extra half-states are added between \$B^1\$ and \$C_1^x\$, adding \$15+16+16 = 47\$ extra steps. Another extra half-state is added between the digit checks and \$B\$, adding 10 extra steps. In total, this machine has 57 extra steps compared to the base machine.
This process can be generalized to any \$n\$-state counter machine.
Note that since \$I^1\$ is unused in the base machine, we already start with a free half-state. This means that we only need at most 1 extra state \$E\$ (aka 2 half-states \$E^0\$ and \$E^1\$).
Code explanation
If you want to take a look at the code, the states are ordered as follow:

Initial state \$I\$
Go back state \$B\$
Digit check states from \$C_1\$ to \$C_b\$
Extra state \$E\$ (if needed)