Fractran is an esoteric Turing-complete programming language invented by John Conway. A Fractran program consists of an ordered list of fractions. The program starts by taking a single integer as input. Each iteration of the program, it searches the list for the first fraction such that multiplying the number by that fraction produces another integer. It then repeats this process with the new number, starting back at the beginning of the list. When there is no fraction on the list that can be multiplied with the number, the program terminates and gives the number as the output.

The reason that Fractran is Turing-complete is because it simulates a register machine. The number's prime factorization stores the contents of the registers, while the division and multiplication is a way to conditionally add and subtract from the registers. I would recommend reading the Wikipedia article (linked to above).

The Challenge

Your task is to write the shortest program possible that can take a valid Fractran program from STDIN as its only input and generates a valid BF program to STDOUT that simulates the Fractran program. There are two ways that you could simulate a Fractran program with BF.

NOTE: Your answer is not a BF program. Your answer is the code that generates the BF program from any given Fractran program. The goal is to get the BF program to be the equivalent of the Fractran program. (technically you could do the competition in BF, but it would be hard)

Option 1

Your program should output a BF program that does the following:

  • Takes exactly 1 number from STDIN in the form of the corresponding ASCII character (due to the way that BF input works), which is the input to the Fractran program.
  • Prints exactly 1 number to STDOUT in the form of the corresponding ASCII character, which is the output to from the Fractran program.

This option is meant to represent the exact input and output from a Fractran virtual machine.

Option 2

The BF code that your program produces should do the following:

  • Take input by having the prime factorization of the number already encoded in memory (prior to running the program). If the input is 28 (2*2*7), then there will be a value of 2 in the second cell and a value of 1 in the seventh cell (the pointer starts on cell 0). All other cells will be zero.
  • Give output by having the prime factorization of the output encoded in memory when the program terminates. If the output is 10, then there must be a value of 1 in each of cells 2 and 5. All other prime-numbered cells must have a value of zero. The content of other cells do not matter.

This option represents the computing model behind the Fractran language.

Rules and Requirements

  1. Input (top your program) will be a list of fractions on STDIN. There will be one fraction per line with a comma between the numerator and denominator. An empty line represents the end of input. The fractions will always be reduced to lowest terms.
  2. Your program's output should be a single-line, valid BF program to STDOUT. This program should be able to simulate that particular Fractran program according to one of the two options. For any input, the BF program generated should be able to produce the same output as the Fractran program.
  3. You must state which option you chose.
  4. You can choose the bounds on the BF memory and tape, and whether they are wrapping
  5. CODE GOLF. Also, the size of the outputted BF programs does not matter, only the size of the program that is doing the converting.
  6. Programs should only consist of printable ASCII

If I am ambiguous anywhere, do not hesitate to ask. This is a very complicated challenge to describe.

In addition, please post your program's generated BF code for the following input, as to provide an easy way to check if your program is working:


This program calculates the number of 1s in the binary expansion of a number. However, the input and output are formatted strangely (as with all Fractran programs). Input is of the form 2^A, while output is of the form 13^B.

  • \$\begingroup\$ So basically you want a fractran interpreter in brainfuck. Everything else is fairly trivial. \$\endgroup\$
    – captncraig
    Commented Mar 19, 2012 at 22:57
  • \$\begingroup\$ @CMP I want a program that outputs the BF version of a Fractran program. The code that does this conversion does not have to be in BF. The BF program itself is single-purpose. \$\endgroup\$
    – PhiNotPi
    Commented Mar 19, 2012 at 23:01
  • 1
    \$\begingroup\$ Are there limits on the brainfuck interpreter we use? Must we use byte sized cells, or can we use int cells? Bounded memory? Wrapping memory? Wrapping cells? Anything we want that makes it work? \$\endgroup\$
    – captncraig
    Commented Mar 19, 2012 at 23:02
  • \$\begingroup\$ Anything you want to make it work, but please specify in your answer. \$\endgroup\$
    – PhiNotPi
    Commented Mar 19, 2012 at 23:03
  • 1
    \$\begingroup\$ It's probably possible to solve this with BF... \$\endgroup\$
    – mbomb007
    Commented Apr 17, 2015 at 14:10

4 Answers 4


Python, 182 chars

Option 1, standard byte cells. There are only 255 possible inputs (0 as an input doesn't really make sense), so I just run a Fractran interpreter 255 times in Python and generate a simple table lookup Brainfuck program encoding the results.

import sys
for i in range(1,256):
 while i:j=i;i=([i*x/y for x,y in I if i%y==0]+[0])[0]
print P+Q

Output for the example input (___ = 246 more nested conditions, I can't paste the whole result as it is too large):

  • 1
    \$\begingroup\$ @PhiNotPi: true, I may need to detect looping and special case that... \$\endgroup\$ Commented Mar 21, 2012 at 1:54
  • 8
    \$\begingroup\$ Actually, I think that determining whether a given Fractran program is an endless loop or not is equivalent to the halting problem. Good luck with that. :) \$\endgroup\$
    – PhiNotPi
    Commented Mar 21, 2012 at 1:58
  • 1
    \$\begingroup\$ An interesting approach. Only shortcoming may be if the fractran spec says it needs to handle outputs greater than 255, which I know many programs rely on, so it seems a bit weird to take only the LSB of the result. \$\endgroup\$
    – captncraig
    Commented Apr 3, 2012 at 18:39
  • 1
    \$\begingroup\$ @CMP, the question specifically states that the input for option 1 is taken from ascii. \$\endgroup\$
    – boothby
    Commented Apr 22, 2012 at 5:28
  • 1
    \$\begingroup\$ @PhiNotPi determining whether or not a program halts, it slightly different than being able to create another program in another language such that it halts if and only if the original halts. The former is impossible, while the latter is done every day by compilers. \$\endgroup\$
    – Cruncher
    Commented Apr 21, 2014 at 19:46

Python, 420 chars

This uses a sort of blend of options 1 and 2: It assumes that brainfuck is implemented with big integers (I use a Sage implementation). Input a fractran program, for example, 33/20,5/11,13/10,1/5,2/3,10/7,7/2. Then, pre-load a number, for example, 2^5, at the cursor. Then, run the output of this python script. Wait 44 seconds. The result, 13^2 sits where the cursor started. I didn't wait for the answer for 2^7.

for l in raw_input().split(','):
print s+">+<[->-<]>[-<+>]<]>>>[-<<<+>>>]"

This is my first brainfuck script. It can certainly be golfed further, but I've got other things to do until later tonight.

edit: rather than golf this further, I'm working on a solution for option 2. also, here's the output for the requested program:

[->>>+<<<]+[[->+>+<<]>[-<+>]>[->[->+>>+<<<]>[-<+>]>>[ [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<<->>>]<<<++>>>]<]<<[->+>+<<]>>[-<<+>>]<[[-]<->]<[<[-]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]<[-]>>[-<<+>>]<<<<<->>>>]<<]<<[->+>+<<]>[-<+>]>[->[->+>>+<<<]>[-<+>]>>[ [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<<->>>]<<<++>>>]<]<<[->+>+<<]>>[-<<+>>]<[[-]<->]<[<[-]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]<[-]>>[-<<+>>]<<<<<->>>>]<<]<<[->+>+<<]>[-<+>]>[->[->+>>+<<<]>[-<+>]>>[ [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<<->>>]<<<++>>>]<]<<[->+>+<<]>>[-<<+>>]<[[-]<->]<[<[-]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]<[-]>>[-<<+>>]<<<<<->>>>]<<]<<[->+>+<<]>[-<+>]>[->[->+>>+<<<]>[-<+>]>>[ [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<<->>>]<<<++>>>]<]<<[->+>+<<]>>[-<<+>>]<[[-]<->]<[<[-]>[-<+>]< [->+>+<<]>[-<+>]<[-]>>[-<<+>>]<<<<<->>>>]<<]<<[->+>+<<]>[-<+>]>[->[->+>>+<<<]>[-<+>]>>[ [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<<->>>]<<<++>>>]<]<<[->+>+<<]>>[-<<+>>]<[[-]<->]<[<[-]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]<[-]>>[-<<+>>]<<<<<->>>>]<<]<<[->+>+<<]>[-<+>]>[->[->+>>+<<<]>[-<+>]>>[ [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<<->>>]<<<++>>>]<]<<[->+>+<<]>>[-<<+>>]<[[-]<->]<[<[-]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]<[-]>>[-<<+>>]<<<<<->>>>]<<]<<[->+>+<<]>[-<+>]>[->[->+>>+<<<]>[-<+>]>>[ [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<->>]<<+[<[-]>-]>>]< [->+>+<<]>>[-<<+>>]<[[-]<-[->+>+<<]>>[-<<+>>]<<>[[-]<<<->>>]<<<++>>>]<]<<[->+>+<<]>>[-<<+>>]<[[-]<->]<[<[-]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]< [->+>+<<]>[-<+>]<[-]>>[-<<+>>]<<<<<->>>>]<<]<<>+<[->-<]>[-<+>]<]>>>[-<<<+>>>]
  • \$\begingroup\$ That's a nice first Brainfuck script, +1. You can compute 2^7 with my Brainfuck interpreter in less than 5 seconds by the way. Also, shouldn't it be raw_input() instead of raw_input (or is it some quirk I don't know about) ? \$\endgroup\$
    – copy
    Commented Mar 22, 2012 at 19:27
  • \$\begingroup\$ @copy, thanks! you're right, raw_input() is necessary. I'm not surprised that competent brainfuck interpreters do better than my awful naive Sage implementation. \$\endgroup\$
    – boothby
    Commented Mar 22, 2012 at 20:46

Perl, 326 characters

I am going to answer my own question hopefully to stimulate more answers. I am of course not eligible to win. This is option 2 with unbounded memory and cells, although it works on wrapping cells. Each fraction is converted into a single block of code. The newlines are for readability.

if($/eq$A){last L}
redo L}print$I

Here is the example output. This takes advantage of the fact that other characters are ignored as comments. This also appears to be a very short output compared to the other entries, although output size doesn't technically matter.


Sage, 431 chars

This is a completely new solution. I figured out some better ways of doing things in brainfuck, and this properly implements Option 2. Newlines added for clarity. This can probably be golfed further, but it involves rewriting the BF to have a lower loop depth.

print '>+[>>>+'+J(map(L(n,m):reduce(Lr,(p,e):'[-%s%s%s[[-]<<+>>]%s<<%s]'%(M(4-p),C(6-p,2),'[-'*(e-1),']'*(e-1),r),f(m),'[-<<<->>>%s]'%J(map(L(p,e):M(4-p)+Q('+-')(e)+M(p-4),f(n/m))))+'<<<'+C(3,2),[map(QQ,x.split('/'))for x in raw_input().split(',')]))+'<<<<+>[-<->]<[->+<]>]'".replace('L','lambda ')

Sample output:

Given the input 33/20,5/11,13/10,1/5,2/3,10/7,7/2


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.