Don’t tell my advisor / employer / students, but I have been playing a lot of the excellent game Factorio lately. Factorio is a factory management simulator where you escape an alien world by automating the harvesting of natural resources to build a rocket. Moreso than most management games, Factorio focuses on the logistical problems of running a supply chain. This can lead to some neat questions.

Take, for example, power generation. Every factory needs power. One very efficient late game technology is nuclear power, which requires the following supply chain:

1. Mine uranium ore.
2. Process uranium ore into uranium-235 and uranium-238.
3. Using both uranium-235 and uranium-238, create uranium fuel cells.

The catch is that step 2 is probabilistic. For each unit of uranium ore that you process, there is a 99.3% chance to obtain uranium-238 and a 0.7% chance to obtain uranium-235. Let’s call these “bad” uranium and “good” uranium, respectively. Step 3 requires that you have 10 bad uranium and 1 good uranium. These probabilities make the setup for nuclear power very slow.

Things liven up once you generate 40 good uranium. Then, via another late-game technology, you can put 40 good uranium into a machine that spits out 41 good uranium. This is 41 total good uranium—the 40 you put in plus one new one. It doesn’t sounds like much but multiplying your supply by $41 / 40$ forever would lead to exponential growth.

Unfortunately, this is not how things work. The process to turn 40 good uranium into 41 good uranium only works on 40 uranium at a time per machine you have to run it. The first time you run it you will have 41 good uranium, but you can only put exactly 40 back into the process. The lone new uranium sits there, useless.

This brings us to the neat question. If you had infinitely many machines to run this process, then the amount of good uranium at step $n$ is given recursively by

What is the asymptotic value of $U_n$?

A good idea is to ignore the floor and guess that the answer is close to $(41 / 40)^n \cdot 40$ anyway. This is wrong, but it’s not that wrong.

Like any good question, you can find a version of this in the OEIS. If, instead of $41 / 40$, you use $3 / 2$, then you will find A061418. This led me to a paper of Odlyzko and Wilf studying similar sequences.

Adapting the ideas in Wilf’s paper, it turns out that $U_n$ is exponential but smaller than $(41 / 40)^n \cdot 40$. There is a constant $c$ such that

So you lose about 43% of your exponential capacity to waiting, but this is still pretty good!

The constant $c$ does not seem to be expressible in terms of anything well-known. There is a “formula,” but it is useless for practical purposes.

Connection to the Josephus problem

Unsurprisingly, Wilf and Odlyzko were not considering uranium processing in Factorio. They were working on a solution to the Josephus problem.

The Josephus problem is this: Arrange $n$ people in a circle and execute every $q$th person until there is only one left. Where should you stand in the initial circle to be the surviving person? This position is called $J_q(n)$. The $q = 2$ case has the famous solution $J_2(n) = 2(n - 2^{\lfloor \log_2 n \rfloor}) + 1$, but there aren’t closed forms beyond that.

Concrete Mathematics has a neat algorithm to solve this problem. Once you pass over someone, move their index to the smallest index not yet seen. (If $q = 3$ then $1$ will become $n + 1$ and $2$ will become $n + 2$.) The last person to be executed will have the label $qn$, so you just need to determine the original index of the person who is eventually labeled $qn$. The sequences of Wilf and Odlyzko help do this.

Our sequence helps solve a similar Josephus-type problem. Arrange $n$ people in a circle and execute every $q$th person starting from the first one. That is, you will always execute the first person, then count off by $q$ from there. Under the same relabeling scheme as before, the last person to be executed will have label $q(n - 1) + 1$. It turns out that the label of this person after going in “reverse” $k$ steps is $qn - U_k^{(q)}$, where $U_k^{(q)}$ is defined by

This sequence solves the problem because we can stop computing as soon as $qn - U_k^{(q)} \leq n$. That is, as soon as $U_k^{(q)} \geq (q - 1)n$.

This sequence is also exactly the same form as our uranium sequence if we set $q = 41$. That is, when we are producing good uranium in Factorio, we are implicitly solving this modified Josephus problem where we execute every forty-first person. If you have $U$ good uranium the first time that you cross $40n$, then then the survivor stood at initial position $41n - U$.

This is not quite proving that Factorio is Turing complete (it is), but it is a neat fact to notice. Factorio has more mathematical depth than any game I’ve played before. I hope that this one example demonstrates that.