Factorio Fractions2019/10/05

Rules of the Game

The game of Factorio involves the transportation of items across transport belts. Here, we are only interested in transporting 1 type of item using belts with unlimited throughput.

Belts are also allowed to cross over each other using underground transport belts.

Lastly, the splitter allows for splitting the items on a transport belt evenly onto 2 transport belts.

The splitter can receive input from two belts at once for convenience. Each side will still be split evenly onto the two output belts.

Playing Around

Using splitters, it is simple enough to create a system that splits off or or of a belt’s items by passing through enough splitters. But complexity arises when there are splitters that feed into each other. In the system below, the top output ends up receiving of the input, and the bottom output receives of the input.

This fancy spiral outputs fractions of and .

As it turns out in all spirals of this style, the first fraction will be the ratio of two consecutive Fibonacci numbers. This will be proved in the next section.

Systems of splitters can also be chained together with the effect of multiplying fractions. Since we know how to make a fraction of , chaining the system twice will result in a fraction of .

Analyzing a System

To see which fraction an output corresponds to, I look at every path an item can take that leads to that output.

In the system above, the top output can be reached by the , , or path.

The path goes through splitter, so of the input follows this path.
The path goes through splitters, so of the input follows this path.
The path goes through splitters, so of the input follows this path.

There are infinitely many possible paths that continue on this pattern, and summing them all gives the total output.

Having splitters arranged in this fashion results in similar calculations.

The system that outputted the fraction is also a tiny “Fibonacci spiral”-type system described in the previous Section. And indeed the output is , the ratio of 2 consecutive Fibonacci numbers. To prove (by induction) that a general spiral with splitters always follows this pattern, the system is simplified in the following way:

The bottom splitters form a spiral of size and is represented by a hypothetical splitter. This splitter has a top split of and a bottom split of . By examining paths again, the top output of this system has output

All Fractions

It turns out that all fractions can be made with a finite number of splitters. First the fraction is written in binary.

The part of the decimal contains 3 digits, and the contains 5 digits, so 8 splitters are used and arranged in the following way:

Every splitter corresponding to a feeds into the top output, while the splitters corresponding to a have their outputs dumped elsewhere. The last splitter also feeds back into one of the previous splitters, to represent the . Since every rational number can be written as a terminating or repeating decimal in binary, every rational number can be represented by some system of splitters.

For an alternative construction of an arbitrary fraction , first the input is evenly split into belts with . Then of those belts are fed back into the beginning. By symmetry, the remaining belts all have an output of . Combining of these belts gives . This construction gives

More Efficient Systems

The method described previously to create all fractions does not always result in a system with the fewest splitters possible. The fraction would use 6 splitters, but only 4 are needed.

To figure out the fewest numbers of splitters needed for common fractions, I searched for all possible fractions made with splitters. With splitters, I found that the fractions are possible.

Analyzing a System 2

There is also a general way to exactly determine which fractions a system will output.

Each splitter and input/output node is named, so that the system can be represented as a graph.

A directed edge represents one splitter feeding into another. Every splitter node has exactly two arrows coming out of it. Since the two outputs of a splitter are equal, they are both labelled the same. The input node only feeds into one splitter, and by assumption, it inputs a into the system.

For every splitter, the inputs must equal the outputs.

With unknowns and equations, the system can be solved to determine the throughput of every edge.

This system outputs the fractions and .

Iterating Over All Systems

In the previous system, the 2nd column of the matrix indicates that the splitter feeds into and splitters. The 5th column indicates that the splitter feeds only into the splitter, so its other output exists the system. It is also possible for a splitter to not feed into any other splitters.

The 1st column and the 1st row are always the same, and there is always a along the diagonal for the rest of the matrix. But in each column, a can appear up to times anywhere else (except the 1st row). For simplicity, I added the restriction that a splitter must feed into at least other splitter. Therefore for a system of splitters, there are such matrices. It is also not necessary to ensure that the resulting graph is planar because of underground belts.

But not all matrices represent valid systems. Here’s one such matrix for splitters.

The splitter has no inputs, so this system is not valid. Fortunately, these matrices are also not invertible.

In the first matrix, the edges , , represented edges that exited the system.

In the graph that this matrix was derived from, and went into the same output, but this information is lost in the matrix. For consistency, it is assumed that when a splitter feeds into an output node, it feeds into its own distinct output node. So this matrix would represent the system

The possible outputs of this system are then all combinations of the outputs , , .

Results

I let my computer calculate all possible fractions for systems of up to splitters. It appears that a system of splitters can always produce the fraction where , although I was unable to prove this. If multiple systems solve a certain fraction, the system with the smallest maximum number of edges going into any one node is preferred. Due to issues with side-loading, these systems are not always possible to represent in Factorio.