I've come across some really interesting things solving Project Euler problems, and FRACTRAN, by John Conway of Game of Life fame, is one of the most interesting of those. It is root of Euler Problem 308, which I'm not going to solve for you (but which should be solvable once you understand how FRACTRAN works, and is fascinating in its own right. I hope I can do it justice in explaining how FRACTRAN works and how you can write programs for it, and then show some examples of programs that can be run with it to solve real problems (if in a somewhat absurd fashion).

What is FRACTRAN?

Much like Life, FRACTRAN produces complex behavior via a very simple set of rules and an initial state. The rules are as follows:

1. Provide an initial seed value and an ordered array of rational numbers (i.e., fractions).
2. Multiply the seed value by the first fraction in the array which will result in a whole number.
   • If none of the fractions multiplied by the seed will result in a whole number, then the current seed is the result.
   • Otherwise, the result of multiplication is the new seed, and you repeat Step #2.

Like I said, it's pretty simple. Implementing FRACTRAN is trivial — here it is as a Ruby function that returns an Enumerator whose last value is the result of the computation (assuming the results are finite):

def fractran(s, program)
  Enumerator.new do |e|
    loop do

      x = program.find { |frac| (s * frac) % 1 == 0 }
      break if x.nil?

      s = (s * x).to_i
      e.yield s

    end
  end
end

This method expects program to be an array of Rational objects, and s to be positive integer. It then finds the first fraction in program that, when multiplied with s, results in an integer, and returns it, where it is then multiplied by s and the loop starts again. If it can't find such a fraction then execution ends.

It's pretty simple. Before explaining how FRACTRAN programs work, let's look at a simple example.

Addition

Perhaps the simplest FRACTRAN program is for addition.

require 'prime'

def fractran_add(a, b)
  n = (2 ** a) * (3 ** b)
  p = [Rational(3, 2)]

  e = fractran(n, p)

  answer = 0
  e.each do |x|
    answer = x
  end

  answer.prime_division.inject({}) {|acc, x| acc[x.first] = x.last; acc}[3]
end

How does it work?

If you haven't guessed already, FRACTRAN is a simple register machine, where the registers are stored in the exponents of the prime factors of s. Because every positive integer has a unique prime factorization, you can be sure that the values in the registers are always distinct despite storing the entire set of registers as a single integer.

I find it much easier to stop thinking about the numbers as numbers, and think of them as the registers they represent. In the addition program above, the fraction 3/2 says that as long as there is a value in Register 2, decrement it and add one to Register 3. As a result, the value of Register 2 is going to be transferred one at a time to Register 3, until finally Register 2 is zero and the program execution ends. The program's result is now stored in Register 3.

Thus, if you push 419904 (2^6 * 3^8) into it, you'll get 4782969 (3^14) out the other side.

This is fundamentally how all FRACTRAN programs work. The only two operations you can perform are:

1. Check and decrement registers
2. Increment registers

The FRACTRAN program for subtraction is similarly simple.

Subtraction

require 'prime'

def fractran_subtract(a, b)
  n = (2 ** a) * (3 ** b)
  p = [Rational(1, 6)]

  answer = 0
  e.each do |x|
    answer = x
  end

  answer.prime_division.inject({}) {|acc, x| acc[x.first] = x.last; acc}[2]
end

Here we again have a single fraction, this time decrementing both Register 2 and Register 3 simultaneously (because 6 == 2^1 * 3^1) until one of them is zero. Since Register 2 should have a larger value than Register 3 (negative numbers can't be directly represented in FRACTRAN, so we have to be sure that everything stays positive), Register 3 should run out first and the result is whatever is left in Register 2.

If you pass 254803968 (2^20 * 3^5) to it, you'll get 32768 (2^15) back.

Multiplication is a bit tougher.

Multiplication

require 'prime'

def fractran_multiply(a, b)
  n = (2 ** a) * (3 ** b)
  p = [Rational(455, 33), 
    Rational(11, 13), 
    Rational(1, 11), 
    Rational(3, 7), 
    Rational(11, 2), 
    Rational(1, 3)]

  e = fractran(n, p)

  answer = 0
  e.each do |x|
    answer = x
  end

  answer.prime_division.inject({}) {|acc, x| acc[x.first] = x.last; acc}[5]
end

For the first time, we have a program that maintains state, and runs different sets of commands depending on the state. Basically, multiplication is repeated adding, which is lucky for us because addition and subtraction are all we can do. But to add repeatedly we need a loop, and that's what state markers come in.

In this multiplication program, the loop is constructed using Registers 11 and 13. Regardless of the input, the first fraction to be hit is 11/2, which decrements Register 2 and increments Register 11. Once Register 11 is set, 455/33 (5^1 * 7^1 * 13^1 / 3^1 * 11^1) unsets Register 11 and decrements Register 3, while setting Register 13 and incrementing Registers 5 and 7. Registers 11 and 13 work together to enable the loop — because checking to see if the state is set (Register 11) is destructive (it reduce Register 11 down to zero), you need another state register that will cause the loop to restart. That's found in the next fraction, 11/13, which simply swaps the values of Register 11 and 13, thereby restarting the loop. This goes on until the value of Register 3 is exhausted (thereby making 455/33 no longer hit), and which point there will be an extra value in Register 11, which is taken care of by 1/11. As a last step, the values accumulated in Register 7 are pushed back into Register 3 by 3/7 (because otherwise Register 3's value would be gone forever — any time you move something from one Register to another, you need to simultaneously move it to a backup location if you want to use it again), and the entire process repeats again, until Register 2 is exhausted. Finally, the excess values in Register 3 are zeroed out, and the answer lives in Register 5.

It may be easier to see what's going on if you look at the result of every step. Here's 3 * 2:

As you can see, even for simple multiplication things get pretty hairy.

Division

require 'prime'

def fractran_divide(a, b)
  n = (2**a) * (3**b) * 11
  p = [Rational(91,66), 
    Rational(11,13), 
    Rational(1, 33), 
    Rational(85, 11), 
    Rational(57, 119), 
    Rational(17, 19), 
    Rational(11, 17), 
    Rational(1, 3)]

  e = fractran(n, p)

  answer = 0
  e.each do |x|
    answer = x
  end

  answer_hash = answer.prime_division.inject({}) {|acc, x| acc[x.first] = x.last; acc}
  if answer_hash[7].nil?
    answer_hash[5]
  else
    Rational((answer_hash[5] * b) + answer_hash[7], b)
  end
end

Division is similar to multiplication, except that it involves repeated subtraction rather than addition. It also gives you the remainder, which is what is left over in Register 7 after the final subtraction.

More FRACTRAN programs

Here are some of the programs I wrote while learning FRACTRAN. They're simple and should be understandable, now that you have the basics of the language down.

# Input: Register 3
# Output: Register 2
# Doubles the input
double = [Rational(4, 3)]

# Input: Register 2, Register 3
# Output: Register 5
# Returns the smaller of the two arguments 
min = [Rational(5, 6), 
  Rational(1, 3), 
  Rational(1, 2)]

# Input: Register 2, Register 3
# Output: Register 5
# Returns the larger of the two arguments
max = [Rational(5, 6), 
  Rational(5, 2), 
  Rational(5, 3)]

# Input: Register 2
# Output: Register 3
# Squares the input
square = [Rational(55, 2), 
  Rational(357, 65), 
  Rational(13, 17), 
  Rational(19, 13), 
  Rational(115, 133), 
  Rational(19, 23), 
  Rational(1, 19), 
  Rational(13, 11),
  Rational(1, 5)]

John Conway's FRACTRAN prime generator

Perhaps the coolest program of them all comes from John Conway himself, in the form of a prime number generator written in FRACTRAN. In just 14 fractions, you can generate every prime number. At each step, if the result is a power of 2 (that is, only Register 2 has values), then the value of Register 2 will be the next prime number. Pretty amazing.

# Input: 2
prime = [
    Rational(17, 91),
    Rational(78, 85),
    Rational(19, 51),
    Rational(23, 38),
    Rational(29, 33),
    Rational(77, 29),
    Rational(95, 23),
    Rational(77, 19),
    Rational(1, 17),
    Rational(11, 13),
    Rational(13, 11),
    Rational(15, 14),
    Rational(15, 2),
    Rational(55, 1)
  ]

It's not the most efficient prime generator you'll ever meet, though. It only takes 19 iterations to find 2, but 69 to find the next prime (3), but a whopping 508,284 iterations to find the 20th prime (71), and the numbers don't get smaller.

This program is also the first infinitely looping FRACTRAN program I've shown you (which is why we built the FRACTRAN implementation as an Enumerator). You can tell that it will run forever because the last fraction isn't actually a fraction, it's a whole number! Thus it will match any input (“Register 1” is always set for any integer), and set Register 5 and 11, thereby restarting the loop again.

Wrapping up

Playing with FRACTRAN is really fun. It's not the most practical thing you'll ever do, but I think that expanding your mind and trying out new things ultimately makes you a better programmer. For more information, check out the Wikipedia page, which was invaluable to me when I was trying to wrap my head around how FRACTRAN works.