A FRACTRAN interpreter implemented in Scala.

FRACTRAN is a Turing-complete esoteric programming language invented by mathematician John Conway. A FRACTRAN program is an ordered list of fractions. The execution is remarkably simple:

1. Start with an integer n
2. Find the first fraction f in the list where n × f is an integer
3. Replace n with n × f and repeat from step 2
4. If no fraction produces an integer, the program halts

Despite its simplicity, FRACTRAN can compute anything a regular computer can.

• Scala 2.13+
• SBT 1.x

sbt compile

sbt "run <number> <fractions>"

Simple execution:

sbt "run 72 455/33,11/13,1/11,3/7,11/2,1/3"

Using power notation for input:

The input number can be expressed as products of powers:

sbt "run 2^3,3^4,2 455/33,11/13,1/11,3/7,11/2,1/3"

This computes 2^3 × 3^4 × 2 = 1296 as the starting value.

Output:

72
396
5460
4620
63700
53900
4900
2100
900
...

For long-running computations, use --progress to see live updates showing the last 3 checkpoints with timestamp, step count, steps/second, and current value:

sbt "run 2^3,3^4,2 455/33,11/13,1/11,3/7,11/2,1/3 --progress"

You can customize the checkpoint interval (default 10000 steps):

sbt "run 2^3,3^4,2 455/33,11/13,1/11,3/7,11/2,1/3 --progress=5000"

Progress output:

FRACTRAN Progress
============================================================

Time               Step      Steps/s   Value
------------------------------------------------------------
10:45:12         10,000     125000.0   8421875
10:45:13         20,000     142857.1   765625
10:45:14         30,000     138888.9   15625

sbt assembly
java -jar target/scala-2.13/fractran.jar 72 "455/33,11/13,1/11,3/7,11/2,1/3"

You can also use the library interactively in the Scala REPL:

# Start REPL with the JAR
scala -cp target/scala-2.13/fractran.jar

Then in the REPL:

import io.github.angleto.fractran._

// Run the addition program: 2^3 * 3^4 -> 2^7
val n = Fract(BigInt(648))  // 2^3 * 3^4
val fractions = LazyList(Fract("2/3"))
Fractran(n, fractions).map(_.div).toList
// List(648, 432, 288, 192, 128)

// Take first 10 results from a longer computation
val program = LazyList(Fract("455/33"), Fract("11/13"), Fract("1/11"), Fract("3/7"), Fract("11/2"), Fract("1/3"))
Fractran(Fract(72), program).take(10).map(_.div).toList

fractran/
├── src/
│   ├── main/scala/io/github/angleto/fractran/
│   │   ├── Fract.scala            # Fraction representation
│   │   ├── Fractran.scala         # Core interpreter
│   │   ├── FractranException.scala
│   │   └── Main.scala             # CLI entry point
│   └── test/scala/                # Test files
├── examples/                      # Example FRACTRAN programs
├── build.sbt
└── README.md

The interpreter uses Scala's LazyList for efficient lazy evaluation, allowing it to handle potentially infinite computation sequences gracefully. The core algorithm:

def apply(n: Fract, fractions: LazyList[Fract]): LazyList[Fract] = {
  def fractran(value: Fract): LazyList[Fract] = {
    fractions.map(f => value * f)
      .find(_.isInt) match {
        case Some(t) => t #:: fractran(t)
        case _       => LazyList.empty[Fract]
      }
  }
  n #:: fractran(n)
}

Computes 2^a × 3^b → 2^(a+b):

sbt "run 2^3,3^4 2/3"

Conway's original FRACTRAN program that generates prime numbers (the PRIMEGAME).

This project is licensed under the GNU General Public License v3.0 - see the LICENSE file for details.

Angelo Leto (@angleto)