This page contains some final thoughts following my quest for 2LBB Busy Beavers.
It an interesting exercise to craft small but long-running programs. Figure 1 shows a relatively small program that runs for a very long time. This program terminates after executing more than 2.882 × 1023409 steps.
Note, the 2LBB program runner on this page is not able to correctly execute the program as it does not support the required data value range. However, for all intents and purposes this program runs forever anyway.
So what does this program do? At the heart is a glider loop. Each iteration it decreases its loop counter by one and increases two counters: the left counter is increased by three and the right counter by five. The right counter becomes the loop counter when the glider loop runs next. The other counter is left in the wake of the glider. This way the glider calculates f(n) = 3 × 5n - 1 for n ≥ 2.
This value is added to the sequence of numbers that is traversed by a sweep loop. This sweep loop decreases all numbers by seven. When the sweep returns to the right of the sequence, the next glider loop runs.
So when does this program terminate, and why does it take so long? The sweep loop checks for each value produced by the glider loop if it is divisable by seven. It determines this via repeated subtraction and terminates when the result is zero. This happens first for f(7) = 234374. It takes 234374 / 7 = 33482 subtractions for this value to reach zero. By then, the last glider loop calculated f(33489) which required 533489 iterations. A glider loop iteration takes 36 steps, so this final loop takes more than 36 × (533489 - 1) > 1023409 steps.