Fractran

Fractran
You are encouraged to solve this task according to the task description, using any language you may know.

FRACTRAN is a Turing-complete esoteric programming language invented by the mathematician John Horton Conway.

A FRACTRAN program is an ordered list of positive fractions $P=(f_{1},f_{2},\ldots ,f_{m})$, together with an initial positive integer input $n$.

The program is run by updating the integer $n$ as follows:

• for the first fraction, $f_{i}$, in the list for which $nf_{i}$ is an integer, replace $n$ by $nf_{i}$ ;
• repeat this rule until no fraction in the list produces an integer when multiplied by $n$, then halt.

Conway gave a program for primes in FRACTRAN:

$17/91$, $78/85$, $19/51$, $23/38$, $29/33$, $77/29$, $95/23$, $77/19$, $1/17$, $11/13$, $13/11$, $15/14$, $15/2$, $55/1$

Starting with $n=2$, this FRACTRAN program will change $n$ in $15=2\times (15/2)$, then $825=15\times (55/1)$, generating the following sequence of integers:

$2$, $15$, $825$, $725$, $1925$, $2275$, $425$, $390$, $330$, $290$, $770$, $\ldots$

After 2, this sequence contains the following powers of 2:

$2^{2}=4$, $2^{3}=8$, $2^{5}=32$, $2^{7}=128$, $2^{11}=2048$, $2^{13}=8192$, $2^{17}=131072$, $2^{19}=524288$, $\ldots$

which are the prime powers of 2.

More on how to program FRACTRAN as a universal programming language will be find in the references.

Your task is to write a program that reads a list of fractions in a natural format from the keyboard or from a string, to parse it into a sequence of fractions (i.e. two integers), and runs the FRACTRAN starting from a provided integer, writing the result at each step. It a also required that the number of step is limited (by a parameter easy to find).

References

J. H. Conway (1987). Fractran: A Simple Universal Programming Language for Arithmetic. In: Open Problems in Communication and Computation, pages 4–26. Springer.

J. H. Conway (2010). "FRACTRAN: A simple universal programming language for arithmetic". In Jeffrey C. Lagarias. The Ultimate Challenge: the 3x+1 problem. American Mathematical Society. pp. 249–264. ISBN 978-0-8218-4940-8. Zbl 1216.68068.

D

Simple Version

Translation of: Java

<lang d>import std.stdio, std.algorithm, std.conv, std.array;

void fractran(in string prog, int val, in uint limit) {

   const fracts = prog.split.map!(p => p.split("/").to!(int[])).array;

   foreach (immutable n; 0 .. limit) {
       writeln(n, ": ", val);
       const found = fracts.find!(p => val % p[1] == 0);
       if (found.empty)
           break;
       val = found.front[0] * val / found.front[1];
   }

}

void main() {

   fractran("17/91 78/85 19/51 23/38 29/33 77/29 95/23
             77/19 1/17 11/13 13/11 15/14 15/2 55/1", 2, 15);

}</lang>

Output:

0: 2
1: 15
2: 825
3: 725
4: 1925
5: 2275
6: 425
7: 390
8: 330
9: 290
10: 770
11: 910
12: 170
13: 156
14: 132

Lazy Version

<lang d>import std.stdio, std.algorithm, std.conv, std.array, std.range;

struct Fractran {

   int front;
   bool empty = false;
   const int[][] fracts;

   this(in string prog, in int val) {
       this.front = val;
       fracts = prog.split.map!(p => p.split("/").to!(int[])).array;
   }

   void popFront() {
       const found = fracts.find!(p => front % p[1] == 0);
       if (found.empty)
           empty = true;
       else
           front = found.front[0] * front / found.front[1];
   }

}

void main() {

   Fractran("17/91 78/85 19/51 23/38 29/33 77/29 95/23
             77/19 1/17 11/13 13/11 15/14 15/2 55/1", 2)
   .take(15).writeln;

}</lang>

Output:

[2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132]

Java

<lang java>import java.util.Vector; import java.util.regex.Matcher; import java.util.regex.Pattern;

public class Fractran{

  public static void main(String []args){ 

      new Fractran("17/91 78/85 19/51 23/38 29/33 77/29 95/23 77/19 1/17 11/13 13/11 15/14 15/2 55/1", 2);
  }
  final int limit = 15;
  

  Vector<Integer> num = new Vector<>(); 
  Vector<Integer> den = new Vector<>(); 
  public Fractran(String prog, Integer val){
     compile(prog);
     dump();
     exec(2);
   }

  void compile(String prog){
     Pattern regexp = Pattern.compile("\\s*(\\d*)\\s*\\/\\s*(\\d*)\\s*(.*)");
     Matcher matcher = regexp.matcher(prog);
     while(matcher.find()){
        num.add(Integer.parseInt(matcher.group(1)));
        den.add(Integer.parseInt(matcher.group(2)));
        matcher = regexp.matcher(matcher.group(3));
     }
  }

  void exec(Integer val){
      int n = 0;
      while(val != null && n<limit){
          System.out.println(n+": "+val);
          val = step(val);
          n++;
      }
  }
  Integer step(int val){
      int i=0; 
      while(i<den.size() && val%den.get(i) != 0) i++;
      if(i<den.size())
          return num.get(i)*val/den.get(i);
      return null;
  }

  void dump(){
      for(int i=0; i<den.size(); i++)
          System.out.print(num.get(i)+"/"+den.get(i)+" ");
      System.out.println();
  }

}</lang>

JavaScript

<lang javascript> var num = new Array(); var den = new Array(); var val ;

function compile(prog){

 var regex = /\s*(\d*)\s*\/\s*(\d*)\s*(.*)/m;
 while(regex.test(prog)){
   num.push(regex.exec(prog)[1]);
   den.push(regex.exec(prog)[2]);
   prog = regex.exec(prog)[3];
 }

}

function dump(prog){

 for(var i=0; i<num.length; i++)
   document.body.innerHTML += num[i]+"/"+den[i]+" ";
 document.body.innerHTML += "
";

}

function step(val){

 var i=0;
 while(i<den.length && val%den[i] != 0) i++;
 return num[i]*val/den[i];

}

function exec(val){

 var i = 0;
 while(val && i<limit){
   document.body.innerHTML += i+": "+val+"
";
   val = step(val);
   i ++;
 }

}

// Main compile("17/91 78/85 19/51 23/38 29/33 77/29 95/23 77/19 1/17 11/13 13/11 15/14 15/2 55/1"); dump(); var limit = 15; exec(2); </lang>

Perl

Instead of printing all steps, I chose to only print those steps which were a power of two. This makes the fact that it's a prime-number-generating program much clearer.

<lang perl>use strict; use warnings; use Math::BigRat;

my ($n, @P) = map Math::BigRat->new($_), qw{ 2 17/91 78/85 19/51 23/38 29/33 77/29 95/23 77/19 1/17 11/13 13/11 15/14 15/2 55/1 };

$|=1; MAIN: for( 1 .. 5000 ) { print " " if $_ > 1; my ($pow, $rest) = (0, $n->copy); until( $rest->is_odd ) { ++$pow; $rest->bdiv(2); } if( $rest->is_one ) { print "2**$pow"; } else { #print $n; } for my $f_i (@P) { my $nf_i = $n * $f_i; next unless $nf_i->is_int; $n = $nf_i; next MAIN; } last; }

print "\n"; </lang>

If you uncomment the

#print $n

, it will print all the steps.

Perl 6

A FRACTRAN program potentially returns an infinite list, and infinite lists are a common data structure in Perl 6. Thus we won't try to enforce a limit to the number of steps.

Notice that this code will only work with a fairly recent version of rakudo, for it requires the .narrow method, which was added in early 2014.

<lang perl6>sub fractran(@r) {

   sub ($n) { ~first Int, map (* *$n).narrow, @r }

}

say .[^20] given 2, fractran(<

   17/91 78/85 19/51 23/38 29/33 77/29 95/23 77/19 1/17 11/13 13/11 15/14 15/2 55/1

>) ...^ ;</lang>

Output:

2 15 825 725 1925 2275 425 390 330 290 770 910 170 156 132 116 308 364 68 4