(Credit: I recently learned of the fruitful fractions from this blog post on The Aperiodical.)
Conway‘s fruitful fractions first appeared as a problem in the Mathematical Intelligencer in 1980 (Reference 1), and are described in more detail in Guy (1983) (Reference 2). The discussion here closely follows that of Reference 2, and the figures in this post are taken from that paper.
The fruitful fractions are a set of 14 innocent-looking fractions:
Consider the following algorithm:
- Start with the input .
- While TRUE (i.e. repeat the steps in the following loop forever):
- Multiply by the leftmost fraction in the row above such that the result is still a whole number.
- If is a pure power of 2, i.e. for some non-negative integer , output the exponent .
It turns out that the output sequence is simply the list of all primes! Here are the steps taken to go from the initial input 2 to the first output 2 (when ):
Amazed?! The rest of this post outlines why this is the case. TLDR: We can reformulate the algorithm above as a flow diagram, which can be interpreted as a computer program that finds all the primes using just 3 types of operations (adding 1 to the contents of a register, subtracting 1 from the contents of a register, and checking if a register is 0).
Step 1: Write out the computer program to generate primes with simple operations
The figure below depicts the computer program that generates all the primes as a flow diagram:
The box in blue (“Is prime?”) is a complex operation which we need to break down even further; the figure below demonstrates how we can do so. For a given , for , we check if divides (i.e. is a divisor of ). If for some , then is composite, otherwise it is prime.
The box in red (“Does ?”) is still too complex: we can break it down further as shown in the figure below. For given and , repeatedly subtract from until we reach a number . If , then , if not does not divide .
If we combine these 3 flow diagrams into one, we get a flow diagram that generates all the primes using 3 simple operations: adding 1 to a variable, subtracting 1 from a variable, and checking if a variable is equal to 0. The rest of the steps will show that the fruitful fractions replicate this flow diagram.
Step 2: Think of ‘s prime factorization as encoding a state
Rewrite the 14 fruitful fractions with their prime factorizations:
It’s not immediately obvious, but one can show that at any point, the number can be written in the form
where are non-negative integers and . We can think of as keeping track of 5 pieces of information, which we write as . Thinking of this as a computer program / machine, represents the state of the machine while are the contents of 4 registers of the machine.
Step 3: Draw the possible transitions between states
Assume that the machine is in a particular state. What other states can the machine reach from there? Each of the 14 fractions corresponds to one state transition, depicted in the state transition diagram below. The numbers in the circle represent the state (the value of ), the letters correspond to the fraction being multiplied, and the numbers correspond to changes to the registers . For example, step B takes the machine from state 17 to state 13, increases and (the 2- and 3-registers) by 1, decreases (the 5-register) by 1, and leaves (the 7-register) unchanged.
Step 4: Amalgamate steps into subroutines
Running through the state diagram several times, you will find that some sequences of steps always happen together: we can amalgamate these into subroutines. For example, in state 19, the machine will make a pair of steps HI times (where is the 2-register), transferring to (the 5-register), and then do step R to arrive at state 11. State 19 can only be reached by step D from state 17 or by step I from state 23, so we can replace stats 19 and 23 by the subroutine
which goes directly from state 17 to state 11. With some work we can come up with the following subroutines:
We can then simplify our original state diagram with these subroutines:
Step 5: Assign meaning to registers and subroutines
This is the trickiest step to work out in my opinion. Notice the following 3 things:
- The sum of the 2- and 5-registers, is always equal to (except when we have finished checking if is prime and are moving on to ).
- The sum of the 3- and 7- registers, is always equal to (except when we have finished checking if and are moving on to checking if ).
- The “Next Number” subroutine is always followed by , the “Decrease Divisor” subroutine is always followed by , and each of these is followed by the “division routine” .
With some tedious work, we can now match our original prime producing flow diagram to the states and subroutines we have developed! The blue and red boxes match with those earlier in this post. (Because of the font face used in this diagram, the variable looks like a slightly bigger version of the variable .)
- Conway, J. H. (1980). Problem 2.4.
- Guy, R. K. (1983). Conway’s Prime Producing Machine.