47 244 577 523

+[>+[[<]<]>-]

Try it online!

To understand how this works we will use the following notation:

42:     +[>$+[[<]<]>-]     1 {2} 3

Where s: is the number of steps taken to reach this state, $ marks where the instruction pointer is (in this case the next instruction is +) and {} marks where the data pointer is. In this example the next state would be 43: +[>+$[[<]<]>-] 1 {3} 3. We will also use "x y"*n to denote n copies of the cells x and y, so the tape 1 "2 3"*3 4 is 1 2 3 2 3 2 3 4.

These are the first few steps of this program:

0:      $+[>+[[<]<]>-]     {0}
2:      +[$>+[[<]<]>-]     {1}
6:      +[>+[[$<]<]>-]     1 {1}
8:      +[>+[[$<]<]>-]     {1} 1
10:     +[>+[[<]$<]>-]     {0} 1 1
12:     +[>+[[<]<]$>-]     {0} 0 1 1
15:     +[$>+[[<]<]>-]     0 {-1} 1 1

That last state can be rewritten as 15: +[$>+[[<]<]>-] "1 0"*0 {-1} 1 1 0 0. Similar states will show up frequently, so we will denote the states s: +[$>+[[<]<]>-] "1 0"*k {-1} 1 m -n n as (s, k, m, n). We can take (15, 0, 1, 0) to be our initial state.

Given one of these (s, k, m, n) states we can compute what happens until a similar state is reached:

s:     +[$>+[[<]<]>-]     "-1 0"*k {-1} 1 m -n n
s+4:   +[>+[[$<]<]>-]     "-1 0"*k -1 {2} m -n n
s+6:   +[>+[[$<]<]>-]     "-1 0"*k {-1} 2 m -n n

Whenever the program is moving left and it encounters a "-1 0", it goes trough it and leaves a "0 -1" behind after 5 steps:

0:  +[>+[[$<]<]>-]     -1 0 {-1}
2:  +[>+[[<]$<]>-]     -1 {0} -1
5:  +[>+[[$<]<]>-]     {-1} 0 -1

Repeating this k times we reach the state:

s+6:      +[>+[[$<]<]>-]     "-1 0"*k {-1} 2 m -n n
s+5k+6:   +[>+[[$<]<]>-]     {-1} "0 -1"*k 2 m -n n
s+5k+8:   +[>+[[<]$<]>-]     {0} -1 "0 -1"*k 2 m -n n
s+5k+10:  +[>+[[<]<]$>-]     {0} 0 -1 "0 -1"*k 2 m -n n
s+5k+13:  +[$>+[[<]<]>-]     0 {-1} -1 "0 -1"*k 2 m -n n

-1 "0 -1"*k can be rewritten as "-1 0"*k -1. Whenever the program is moving right and it encounters a "-1 0", it goes trough it and leaves a "-1 0" behind after 6 steps:

0:   +[$>+[[<]<]>-]     {-1} -1 0
3:   +[>+[[<]<]$>-]     -1 {0} 0
6:   +[$>+[[<]<]>-]     -1 0 {-1}

Now we repeat this k times:

s+5k+13:   +[$>+[[<]<]>-]     {-1} "-1 0"*k -1 2 m -n n
s+11k+13:  +[$>+[[<]<]>-]     "-1 0"*k {-1} -1 2 m -n n

It is worth noting that going from +[>+[[$<]<]>-] "-1 0"*k {-1} to +[$>+[[<]<]>-] "-1 0"*k {-1} -1 took 11k+7 steps.

s+11k+13:  +[$>+[[<]<]>-]     "-1 0"*k {-1} -1 2 m -n n
s+11k+19:  +[$>+[[<]<]>-]     "-1 0"*k -1 0 {1} m -n n
s+11k+21:  +[>+$[[<]<]>-]     "-1 0"*k -1 0 1 {m+1} -n n

Now we are testing whether m+1 is 0, we will consider the case m-1!=0 first:

s+11k+21:  +[>+$[[<]<]>-]     "-1 0"*k -1 0 1 {m+1} -n n
s+11k+30:  +[>+[[$<]<]>-]     "-1 0"*k {-1} 0 1 m+1 -n n
s+22k+37:  +[$>+[[<]<]>-]     "-1 0"*k {-1} -1 0 1 m+1 -n n (skipping the 11k+7 steps)
s+22k+43:  +[$>+[[<]<]>-]     "-1 0"*k -1 0 {-1} 1 m+1 -n n
s+22k+43:  +[$>+[[<]<]>-]     "-1 0"*(k+1) {-1} 1 m+1 -n n

So we found out that from the state (s, k, m, n) we reach the state (s+22k+43, k+1, m+1, n) if m+1 is not 0. If m+1 is 0, then instead we have:

s+11k+21:  +[>+$[[<]<]>-]     "-1 0"*k -1 0 1 {0} -n n
s+11k+24:  +[>+[[<]<]>-$]     "-1 0"*k -1 0 1 0 {-n-1} n

Now we are testing whether -n-1 is 0. If it is 0, then from the state (s, k, 1, 1) we reach the state (s+11k+25, k+1, 0, 0) and halt. If it is not 0, then this is what happens:

s+11k+24:  +[>+[[<]<]>-$]     "-1 0"*k -1 0 1 0 {-n-1} n
s+11k+41:  +[>+[[$<]<]>-]     "-1 0"*k {-1} 0 1 0 -n-1 n+1
s+22k+48:  +[$>+[[<]<]>-]     "-1 0"*k {-1} -1 0 1 0 -n-1 n+1
s+22k+54:  +[$>+[[<]<]>-]     "-1 0"*k -1 0 {-1} 1 0 -n-1 n+1
s+22k+54:  +[$>+[[<]<]>-]     "-1 0"*(k+1) {-1} 1 0 -(n+1) n+1

So from the state (s, k, m, n) we reach (s+22k+54, k+1, 0, n+1).

Now that we understand how the program behaves we can compute that it takes 47244577523 steps to halt instead of having to run it. We can also verify that it's correct by changing the cell size to smaller values and confirming that the prediction matches the number of steps.

Bonus: +[+[>-[<]]->] halts in 3 690 185 667 steps

How this was found

The part about all the trial and error with different loop detection algorithms and filters is irrelevant, so I'll instead explain how this could have been found given hindsight.

The idea is to generate a list of programs and then start eliminating them until we are left with a list small enough to be dealt with manually. If we consider all the ways to combine 13 characters, then we are looking at \$7^{13}\$ \$\approx\$ 97 billion programs. If instead we consider only the combinations where each [ matches a ], then this number drops to 8.6 billion. This restriction by itself eliminated 91% of all programs we would have needed to consider, but this can be taken much further. Besides eliminating programs that loop, we also want to eliminate equivalent programs like +[+>-<], +[+<->], -[-<+>] and -[->+<], leaving only one canonical representative of each group to avoid repeated work. Here is a list of filters we can apply:

• Programs that contain +-, -+, <> or >< anywhere can be eliminated because they could have used .. instead. Example: +[++-] \$\rightarrow\$ +[+..]

• Programs that contain [] either loop or could have used ... Example: +>[] \$\rightarrow\$ +>..

• Programs that contain +., -., <. or >. could have used .+, .-, .< or .>. Example: +[+..] \$\rightarrow\$ +[..+]

• Programs that contain ][ can be eliminated since it's impossible to enter the second loop, so they are suboptimal. Example: +[>][<]

• Programs that contain ]. either don't enter the loop and should be eliminated or they enter the loop and could have used .] instead, so they are bad either way. Example: +[+]. \$\rightarrow\$ +[+.]

• With the above filters the nops can only come after a [ or another nop, so if a program contains .] we know that the loop only contains nops and the program can be eliminated for the same reason we banned []. Example: +[..]

  • Writing this I realized that we could have also eliminated programs that include .[, since it implies that there are 2 loops starting, so the inner loop will always be entered and the nops could be moved there. Example: +[.[>]-] \$\rightarrow\$ +[[.>]-]. Now I already ran all the code, so pretend this rule doesn't exist. This filter by itself would have eliminated around 2.67% of the remaining candidates before execution and 2.63% of the candidates in the final list.

• The first command must be a +. The programs starting with - can be eliminated by equivalence, the ones starting with <, > or . could have used . and moved to the end of the program and the ones starting with [ cannot enter the loop. Examples: -[-] \$\rightarrow\$ +[+], >+[+] \$\rightarrow\$ +[+].

• The last command must be a ]. The programs that end with +, -, < or > could have used . and the programs ending in . can be eliminated for the same reason we eliminated ]. anywhere in the program. Example: +[+]> \$\rightarrow\$ +[+].

• Programs where the first shift is to the left can be eliminated by equivalence. (here "first" means in the code, not during execution) Example: +[-[<]+>+] \$\rightarrow\$ +[-[>]+<+]

• With the above filters the nops can only come in groups after each [, we can eliminate programs with multiple groups because either all groups are executed the same number of times, in which case we can put all nops in the first group, or they are executed a different number of times, in which case we can move all nops to the group that gets executed the most. Example: +[..>-[.-<]+] \$\rightarrow\$ +[...>-[-<]+] or +[>-[...-<]+]

• If all the shifts have a common denominator, then some cells of the tape are not used and the program is suboptimal. Example: +[-[>>>]+<<<] \$\rightarrow\$ +[-[>]+<]

• The code between the end of the last two loops should move the data pointer to a new cell. If a program ends in something like ]>+<-], then we know that before the >+<- the pointer was at a 0 cell, and after the >+<- it will always have the same value (in this case -1). If the value is 0, then the outer loop is useless, if the value is not 0, then it is impossible to leave the outer loop. Examples: +[>+[+]], +[>+[<]-]

• If the program contains two nested loops without any code between them, one of them could have been nops. Example: +[[+]] \$\rightarrow\$ +[.+.]

• If a loop starts after another loop and ends after another loop, then it could have been nops. Example: -[[>+[<]]>++] \$\rightarrow\$ -[.>+[<].>++]

• If all + and - happen after a ], then only the 0 cells can change value, so by equivalence we can eliminate all programs that write something other than 1. Example: +[>[>]-[<]++] \$\rightarrow\$ +[>[>]+[<]+]

With these 15 filters we can bring the number of candidates from 8.6 billion down to 2 million (-99.977%). But the programs left after this still suck, ++++++++++[+], for example, is still in our list of candidates.

The next step is to run these programs to eliminate those that loop and those that halt too soon. For loop detection we can use Brent's cycle detection algorithm. But testing whether the state of the program repeated exactly wouldn't rule out enough programs. So given the two states tortoise and hare, we can use the following algorithm to detect any cycle with constant length:

1. If the instruction pointers are in different parts of the program, then this is not a loop.
2. Let t be the number of steps between the tortoise and the hare.
3. Determine the direction the data pointer moved in those t steps between these states.
   • If the pointer is in the same cell in both states, then compare the values of the cells that have been visited in the last t steps up to the tortoise and the values of the cells that have been visited in the last t steps up to the hare. If all these cells have the same value, then the program loops with a period of t without ever visiting new cells.
   • If the pointer moved to the right, then compare the values of all cells to the right of the pointer in both states and compare the values of the cells to the left that have been visited in the last t steps in both states. If all these cells have the same value, then the program loops with a period of t while moving to the right.
   • If the pointer moved to the left, then use the same test for moving right. (with left/right swapped of course)

Now we can run these 2 million programs for 20 million steps while looking for loops to get a list of programs that either halt after 20 million steps or loop. While we are at it we can do the same with lengths other than 13. These are the numbers of candidates left after each step:

We can then go through each one of the remaining programs by hand to see if they halt. For length 10 the only remaining program is +[>-[<]+>], which is the shortest program that loops without a constant cycle length. For lengths 11 and 12 I've also confirmed manually that they also loop. With this we can conclude that these are the busy beavers (some of these step counts can be reached with completely different programs):

For length 13 we have 418 programs left to test (a 99.979% reduction from the 2 million), many of them obviously loop (e.g. ++[+[>]+[<]>]) and many of them are suboptimal (e.g. +[>+[<]-]+[+]), removing these obvious cases manually leaves around 200 programs. Most of them are about as complex as that 47 billion step program, they have one or two counters that are incremented while extending a repeating pattern of cells. We can use this to our advantage, if we run these program again but with a smaller cell size like 16 or 8, then the counters will reach 0 sooner and we can detect programs that would have halted much later with cell sizes of 256. Doing this for a few different sizes reveals that +[+[>-[<]]->], +[>>+>+[<]->], +[>>->-[<]+>], +[>+[[<]<]>-] and +[>-[-<]+>++] are worth exploring first. +[+[>-[<]]->] halts in 3.7 billion steps, +[>+[[<]<]>-] halts in 47 billion steps and +[>-[-<]+>++] loops. +[>>+>+[<]->] and +[>>->-[<]+>] on the other hand have a much more chaotic behaviour, they follow basically the same rules but with different starting numbers. These programs somehow manage to implement some sort of binary/base 5 counter that is not used to waste time, but to decide which of 4 different counters is going to be incremented next. Once one of these counters reaches 0 it simply creates new counters and continues incrementing them irregularly. I highly recommend taking a look at these two running. Sadly they both loop, with a constant cycle length even (11 699 886 and 20 166 302 steps respectively), but for a lot of cell sizes they do halt.

If you are interested you can find the list of of programs that need to be checked manually and the list of "non-equivalent" busy beavers for lengths up to 11 here. It also includes a quick implementation of all the algorithms I mentioned here (does not include that new filter I mentioned), but it's mostly just a slightly less rushed version of the code I used, so I would recommend reimplementing everything from scratch to find more busy beavers.

Update: I finished going through all remaining programs with length 13 manually, that 47 billion step program should be the busy beaver.

A lot of programs that loop either use a constant amount of space or the space is proportional to the number of steps. These programs can usually be eliminated by that cycle detection algorithm. For most of the remaining programs the space is proportional to the square root of the number of steps. This is achieved by extending a repeating pattern of cells and constantly moving over these cells, like that 47 billion step program does with the repeating -1 0 cells. But for the programs +[>+[+<<]>>-] and -[>+[+<<]>>-] the space used is proportional to the logarithm of the number of steps (by adding >> at the start of these programs they also become compatible with tapes that are infinite in only one direction). They manage to implement a base 255 counter that keeps incrementing forever, but they can be stopped by placing a 1 in specific places in the tape. So we can use the program + "<<<"*n -[>+[+<<]>>-] (where "<<<"*n means n copies of <<<) to show that \${BB}_{BF}(3n+14) \ge \dfrac{424320 \cdot 255^n - 680720 n - 375933}{16129}\$. I think that this is the most interesting behaviour among all programs with length up to 13.

The 14 byte program +[>+[>]-<+<<-] apparently halts after 216 quadrillion steps (in less than a second!). It actually loops with a cycle length of 22 and uses more than the allocated tape, but other than that I don't know what is going on.

4977

Just dropping my 13-byte beast to raise the bar. This ain’t your average tweak — it’s a full-on nested loop chaos generator that wracks up 4,977 steps before calling it quits. Pointer auto-increment + inner loop pointer bounce = mad step inflation.

-[[>+[<]]>++]

Not messing around here. This one exploits the pointer behavior perfectly, looping 255 times with pointer jumps that make your CPU sweat. Infinite tape, 8-bit wrapping cells, and a step count to make your head spin.

You can Verify the count Here

16808334

Just to get things started, though I'm not very good at Brainfuck so someone can probably find something better. Not much to say here, I just took the 9-byte example and shoehorned in a small 4-byte decrement loop -[-] in the middle that adds 512 instructions each time it's reached.

+[+[>]-[-]-<]

Code I wrote up to measure instruction count, not sure if 100% accurate or not