Busy Beavers

There is a special kind of Turing machines called the Busy Beavers.

A Busy Beaver is a machine defined for P symbols and Q states.
Its purpose is to write as many symbols as possible on the tape.

Let's take an example with a 2 symbols and 2 states Busy Beaver.

It is described by a $P\times Q$ matrix.

 Symbol|      State-1      |      State-2
       | Write Move   Next | Write Move   Next
----------------------------------------------
 0     |    1   R       2  |   1    L      1
 1     |    1   L       2  |   1    R      0

Each row corresponds to a symbol read on the tape.
Each column corresponds to a state and contains a triple:
- Which symbol to write on the tape
- In which direction to move (Left or Right) on the tape
- Next state. (State 0 means the Beaver halts.)

Example: if we read a '0' on the tape, and we are is state 2, we write a '1' on the tape, the the Left and go to state 1.
We always starts with an empty tape (filled with '0'), and in state 1.

If we run this Busy Beaver, we get the following execution trace:

Step Curr Tape            Move Write Next
 0   1    00000{0}000000  R    1     2
 1   2    000001{0}00000  L    1     1
 2   1    00000{1}100000  L    1     2
 3   2    0000{0}1100000  L    1     1
 4   1    000{0}11100000  R    1     2
 5   2    0001{1}1100000  R    1     0

The beaver stops after 6 steps and in the end the tape contains 4 '1'.

This is actually the "best" $2\times 2$ Busy Beaver (the one which writes the more '1' on a tape).

Let's take a $2\times 6$ Busy Beaver, defined with the following matrix:

 Symb|     State-1   |     State-2   |   State-3     |   State-4     |   State-5     |   State-6
     |Write Move Next|Write Move Next|Write Move Next|Write Move Next|Write Move Next|Write Move Next
-----------------------------------------------------------------------------------------------------
 0   |   1   L     2 |  1    R     3 |  0    R     6 |  1    L     1 |  0    L     1 |  1    L     5 
 1   |   1   L     1 |  1    R     2 |  1    R     4 |  0    R     5 |  1    R     3 |  1    L     0 

You can verify that this beaver halts after 13,122,572,797 steps (took me 400 sec).

How many steps does it need to write 100000 '1'

You are given:
- 3726 steps for 100 '1'
- 315587 steps for 1000 '1'

[My timing: 84 sec]