Tutorial:Prime splitter arrays

1-5th splitter array — A simple 1/5th splitter array

Prime splitter arrays are a type of load balancer, splitting one conveyor belt input into a prime number of outputs. This can help in creating efficient production lines where a prime number of outputs (e.g. to machines) is needed. Splitter arrays and balancers in general differ from manifolds, in that they fill every output simultaneously and don't require the first outputs in line to overfill.

The problem[]

Conveyor Splitters can only split one input into one, two, or three outputs. This makes it easy to create load balancers with outputs that are multiples of these (e.g. 4,6,8,9,...) by chaining splitters. Prime numbers (by nature of being prime) on the other hand cannot be made from the simple chaining of splitters, requiring more complex arrays including "loop back", where one splitter moves items to a Conveyor Merger at a previous step in the array.

So the problem is: What set of Splitters and Mergers creates outputs of 1/p of the input, where p is the wanted prime number of outputs?

Solution[]

The solution presented here, is to split the input into two, on part being a 1/p fraction of the input and the other being the remaining (p-1)/p of the input. The second output is then not prime and can be balanced further through more simple means. The entire setup consist of a line (or array) of mergers and splitters subdividing the input until the desired fraction 1/p is achieved.

Proof of existence[]

Here is a (not quite rigorous) proof that, such a setup exists. A way to create splitter arrays is given in the segment below.

The problem can be simplified by saying the total input is 1 and viewing each Merger and Splitter as either adding to or dividing the throughput, e.g. a Splitter might create two outputs of $\frac{1}{2}$ each. The goal is to find an array a of n divisions or additions, such that $a_n = \frac{1}{p}$ . Without loss of generality, the last step can be assumed to be a Splitter, dividing the input by 2 or 3. This means the array's last step (step #n) is:

$a_n = \frac{a_{n-1}}{s} = \frac{1}{p} \iff a_{n-1} = \frac{s}{p} \qquad s\in[2,3]$

Or in other words: The input from the second to last step $a_{n-1}$ has to be $\frac{s}{p}$ . This is the same statement as before, just scaled by s. It follows, that a row of Splitters can produce the output $a_n = \frac{1}{p}$ , for any input ${\textstyle \text{in}}$ , that follows:

$\text{in} = \frac{q}{p}$

where q is a multiple of 1, 2 and 3. The problem becomes, to form such an input. By chaining enough Splitters q becomes large than p, and:

$\text{in} = \frac{q}{p} \ \stackrel{q > p}{\Longrightarrow} \ \text{in} = 1 + \frac{q'}{p}$

where the new q' is a multiple of 1,2 and 3 too. The input of 1 can come from the total input into the array and the $\frac{q'}{p}$ part can be made, by merging outputs from Splitters. This is always possible, as the splitters themselves only produce fractions that are multiples of 1,2, and 3. Therefore, for any desired prime number p (actually any whole number) there exists a row of Mergers and Splitters such that the reciprocal of p is the output. It also follows, that the array consists first of a row of mergers creating a throughput of $1 + \frac{q'}{p}$ which then feeds into a row of splitters dividing this into the desired fraction of $\frac{1}{p}$ .

Creating the array[]

This is a simple algorithm for creating a prime splitter array. It works by keeping track of the Splitter outputs and a number c:

Start at the output. This will be 1/p in the end. Set c to 1/p.
Add a Splitter
- One belt goes into the previous step
- All other belts will be set aside for later
- Write down the output of each belt (this is c)
- Multiply c by the number of outgoing belts
If c less than 1 repeat step 2. Try to make c as close to 1 as possible.
If c is greater than 1 add the necessary Mergers
- Subtract 1 from c
- The remaining c has to be made up from adding the output of the splitters
- All other remaining Splitter-outputs add up to (p-1)/p

For example a 1/11 splitter array can be constructed as such:

1 to 11 load balancer — 1:11 prime splitter array. Rounded squares are Mergers, squares Splitters.

Set c to 1/11
Add a three-way Splitter (c = 3/11)
Add a two-way Splitter (c = 6/11)
Add another two-way splitter (c = 12/11)
Because c is now greater than 1 add a merger and belt the input to it
Remove 1 from c, c is now 1/11. This is what we additionally have to move into the merger
(Optional) Merge all remaining belts into one 10/11 belt.

Examples[]

1 to 5[]

1 to 5 setup
1 to 5 diagram

1 to 11[]

1 to 11 setup
1 to 11 diagram

1 to 13[]

1 to 13 setup
1 to 13 diagram

Problems[]

This approach is not perfect, but it works for all prime numbers. Because the idea is to simplify the problem of creating one big 1:p load balancer into two easier steps (making on 1/p belt and (p-1)/p belt, subdividing the (p-1)/p belt) the entire setup becomes quite large. There exist^[where?] "all-in-one" solutions for 1:p load balancers that are smaller and less costly.

Additionally, due to the "loop-back" the belt directly after the merger carries more items per minute than the input belt. This means splitter arrays create a bottleneck and have to be supplied by a belt with empty slots. Also, the "loop-back" adds a slight delay, during which the splitter array has a slightly lower throughput than designed.