Fractran

From Rosetta Code
Revision as of 04:44, 21 January 2014 by rosettacode>Gerard Schildberger (→‎{{header|REXX}}: removed some dead code. -- ~~~~)
Task
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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P = (f_1, f_2, \ldots, f_m)} , together with an initial positive integer input Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} .

The program is run by updating the integer Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} as follows:

  • for the first fraction, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f_i} , in the list for which Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle nf_i} is an integer, replace Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} by Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle nf_i}  ;
  • repeat this rule until no fraction in the list produces an integer when multiplied by Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} , then halt.

Conway gave a program for primes in FRACTRAN:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 17/91} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 78/85} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 19/51} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 23/38} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 29/33} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 77/29} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 95/23} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 77/19} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1/17} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 11/13} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 13/11} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 15/14} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 15/2} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 55/1}

Starting with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=2} , this FRACTRAN program will change Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 15=2\times (15/2)} , then Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 825=15\times (55/1)} , generating the following sequence of integers:

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 15} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 825} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 725} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1925} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2275} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 425} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 390} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 330} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 290} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 770} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \ldots}

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

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^2=4} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^3=8} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^5=32} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^7=128} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{11}=2048} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{13}=8192} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{17}=131072} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2^{19}=524288} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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) { Failure R// 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

>) ...^ Failure;</lang>

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

REXX

Programming note:   extra blanks can be inserted in the fractions before and/or after the solidus   [/]. <lang rexx>/*REXX pgm runs FRACTAN for a given set of fractions and from a given N.*/ numeric digits 100 /*be able to handle larger nums. */ parse arg N terms fracs /*get optional arguments from CL.*/ if N== | N==',' then N=2 /*N specified? No, use default.*/ if fracs= then fracs= , /*any fractions specified? No···*/ '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' f=fracs /* [↑] use default for fractions.*/ 

       do i=1  while f\==;   parse var f @.i ',' f
       end   /*i*/                    /* [↑]   parse all the fractions.*/
  1. =i-1 /*the number of fractions found. */

say # 'fractions:' fracs /*display # and actual fractions.*/ say 'N is starting at:' N /*display the starting number N.*/ if terms== | terms==',' then terms=100 /*¬ specified? Use default.*/ say terms 'terms being shown:' /*display a kind of header/title.*/ say; do j=1 for terms /*perform loop once for each term*/ 

          do k=1  for  #;  interpret '_=' N "*" @.k   /* [↓]  integer? */
          if \datatype(_,'W')  then iterate   /*Not integer?   Skip it.*/
          say right(j||th(j),15) 'term: '  N  /*display formatted term.*/
          N=_                         /*set the next  N  to be used.   */
          leave                       /*go start calculating next term.*/
          end   /*k*/                 /* [↑]  if integer, found a new N*/
       end      /*j*/

exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────TH subroutine───────────────────────*/ th: procedure;parse arg x;x=abs(x);return word('th st nd rd',1+x//10*(x//100%10\==1)*(x//10<4))</lang> output using the default input: 

14 fractions: 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
N is starting at: 2
100 terms being shown:

            1st term:  2
            2nd term:  15
            3rd term:  825
            4th term:  725
            5th term:  1925
            6th term:  2275
            7th term:  425
            8th term:  390
            9th term:  330
           10th term:  290
           11th term:  770
           12th term:  910
           13th term:  170
           14th term:  156
           15th term:  132
           16th term:  116
           17th term:  308
           18th term:  364
           19th term:  68
           20th term:  4
           21st term:  30
           22nd term:  225
           23rd term:  12375
           24th term:  10875
           25th term:  28875
           26th term:  25375
           27th term:  67375
           28th term:  79625
           29th term:  14875
           30th term:  13650
           31st term:  2550
           32nd term:  2340
           33rd term:  1980
           34th term:  1740
           35th term:  4620
           36th term:  4060
           37th term:  10780
           38th term:  12740
           39th term:  2380
           40th term:  2184
           41st term:  408
           42nd term:  152
           43rd term:  92
           44th term:  380
           45th term:  230
           46th term:  950
           47th term:  575
           48th term:  2375
           49th term:  9625
           50th term:  11375
           51st term:  2125
           52nd term:  1950
           53rd term:  1650
           54th term:  1450
           55th term:  3850
           56th term:  4550
           57th term:  850
           58th term:  780
           59th term:  660
           60th term:  580
           61st term:  1540
           62nd term:  1820
           63rd term:  340
           64th term:  312
           65th term:  264
           66th term:  232
           67th term:  616
           68th term:  728
           69th term:  136
           70th term:  8
           71st term:  60
           72nd term:  450
           73rd term:  3375
           74th term:  185625
           75th term:  163125
           76th term:  433125
           77th term:  380625
           78th term:  1010625
           79th term:  888125
           80th term:  2358125
           81st term:  2786875
           82nd term:  520625
           83rd term:  477750
           84th term:  89250
           85th term:  81900
           86th term:  15300
           87th term:  14040
           88th term:  11880
           89th term:  10440
           90th term:  27720
           91st term:  24360
           92nd term:  64680
           93rd term:  56840
           94th term:  150920
           95th term:  178360
           96th term:  33320
           97th term:  30576
           98th term:  5712
           99th term:  2128
Retrieved from "https://rosettacode.org/wiki/Fractran?oldid=238976"