Fractran: Difference between revisions

Content added Content deleted

Inline

Revision as of 19:52, 21 March 2014

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$ with $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$ to $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.

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 is also required that the number of step is limited (by a parameter easy to find).

Extra credit: Use this program to derive the first 20 or so prime numbers.

For more on how to program FRACTRAN as a universal programming language, see:

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.

Number Pathology: Fractran by Mark C. Chu-Carroll; October 27, 2006.

Ada

<lang Ada>with Ada.Text_IO;

procedure Fractan is

  type Fraction is record Nom: Natural; Denom: Positive; end record;
  type Frac_Arr is array(Positive range <>) of Fraction;
  
  function "/" (N: Natural; D: Positive) return Fraction is
     Frac: Fraction := (Nom => N, Denom => D);
  begin
     return Frac;
  end "/";
  
  procedure F(List: Frac_Arr; Start: Positive; Max_Steps: Natural) is
     N: Positive := Start;
     J: Positive;
  begin
     Ada.Text_IO.Put(" 0:" & Integer'Image(N) & "   ");
     for I in 1 .. Max_Steps loop

J := List'First; loop if N mod List(J).Denom = 0 then N := (N/List(J).Denom) * List(J).Nom; exit; -- found fraction elsif J >= List'Last then return; -- did try out all fractions else J := J + 1; -- try the next fraction end if; end loop; Ada.Text_IO.Put(Integer'Image(I) & ":" & Integer'Image(N) & " ");

     end loop;
  end F;

begin

  -- F((2/3, 7/2, 1/5, 1/7, 1/9, 1/4, 1/8), 2, 100); 
  -- output would be "0: 2    1: 7    2: 1" and then terminate

  F((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);
  -- output is "0: 2    1: 15    2: 825    3: 725   ...   14: 132    15: 116"

end Fractan;</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    15: 116

AutoHotkey

<lang AutoHotkey>n := 2, steplimit := 15, numerator := [], denominator := [] s := "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"

Loop, Parse, s, % A_Space

   if (!RegExMatch(A_LoopField, "^(\d+)/(\d+)$", m))
       MsgBox, % "Invalid input string (" A_LoopField ")."
   else
       numerator[A_Index] := m1, denominator[A_Index] := m2

SetFormat, FloatFast, 0.0 Gui, Add, ListView, R10 W100 -Hdr, | SysGet, VSBW, 2 LV_ModifyCol(1, 95 - VSBW), LV_Add( , 0 ": " n) Gui, Show

Loop, % steplimit {

   i := A_Index
   Loop, % numerator.MaxIndex()
       if (!Mod(nn := n * numerator[A_Index] / denominator[A_Index], 1)) {
           LV_Modify(LV_Add( , i ": " (n := nn)), "Vis")
           continue, 2
       }
   break

}</lang> Output:

Bracmat

This program computes the first twenty primes. It has to do almost 430000 iterations to arrive at the twentieth prime, so instead of immediately writing each number to the terminal, it adds it to a list. After the set number of iterations, the list of numbers is written to a text file numbers.lst (21858548 bytes), so you can inspect it. Because it takes some time to do all iterations, its is advisable to write the source code below in a text file 'fractran' and run it in batch mode in the background, instead of starting Bracmat in interactive mode and typing the program at the prompt. The primes, together with the largest number found, are written to a file FRACTRAN.OUT. <lang bracmat>(fractran=

 np n fs A Z fi P p N L M

. !arg:(?N,?n,?fs) {Number of iterations, start n, fractions}

 & :?P:?L                           {Initialise accumulators.}
 &   whl
   ' ( -1+!N:>0:?N                  {Stop when counted down to zero.}
     & !n !L:?L                     {Prepend all numbers to result list.}
     & (2\L!n:#?p&!P !p:?P|)        {If log2(n) is rational, append it to list of primes.}
     & !fs:? (/?fi&!n*!fi:~/:?n) ?  {This line does the following (See task description):
                                     "for the first fraction, fi, in the list for which
                                      nfi is an integer, replace n by nfi ;"}
     )
 & :?M
 & whl'(!L:%?n ?L&!n !M:?M)         {Invert list of numbers. (append to long list is
                                     very expensive. Better to prepend and finally invert.}
 & (!M,!P)                          {Return the two lists}

);

( clk$:?t0 & fractran$(430000, 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)

 : (?numbers,?primes)

& lst$(numbers,"numbers.lst",NEW) & put$(" FRACTRAN found these primes:"

 !primes
 "\nThe list of numbers is saved in numbers.txt

The biggest number in the list is"

 (   0:?max
   & !numbers:? (>%@!max:?max&~) ?
 | !max
 )

str$("\ntime: " flt$(clk$+-1*!t0,4) " sec\n") , "FRACTRAN.OUT",NEW) );</lang> In Linux, run the program as follows (assuming bracmat and the file 'fractran' are in the CWD):

./bracmat 'get$fractran' &

Output in FRACTRAN.OUT:

FRACTRAN found these primes:
  1
  2
  3
  5
  7
  11
  13
  17
  19
  23
  29
  31
  37
  41
  43
  47
  53
  59
  61
  67

The list of numbers is saved in numbers.txt
The biggest number in the list is
  1842775069354845065175076326808495219647033145169559640049770986129640260031692378106527030467987060546875

time: 1,8668*10E3 sec

C

Using GMP. Powers of two are in brackets. For extra credit, pipe the output through | less -S. <lang c>#include <stdio.h>

include <stdlib.h>
include <gmp.h>

typedef struct frac_s *frac; struct frac_s { int n, d; frac next; };

frac parse(char *s) { int offset = 0; struct frac_s h = {0}, *p = &h;

while (2 == sscanf(s, "%d/%d%n", &h.n, &h.d, &offset)) { s += offset; p = p->next = malloc(sizeof *p); *p = h; p->next = 0; }

return h.next; }

int run(int v, char *s) { frac n, p = parse(s); mpz_t val; mpz_init_set_ui(val, v);

loop: n = p; if (mpz_popcount(val) == 1) gmp_printf("\n[2^%d = %Zd]", mpz_scan1(val, 0), val); else gmp_printf(" %Zd", val);

for (n = p; n; n = n->next) { // assuming the fractions are not reducible if (!mpz_divisible_ui_p(val, n->d)) continue;

mpz_divexact_ui(val, val, n->d); mpz_mul_ui(val, val, n->n); goto loop; }

gmp_printf("\nhalt: %Zd has no divisors\n", val);

mpz_clear(val); while (p) { n = p->next; free(p); p = n; }

return 0; }

int main(void) { run(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");

return 0; }</lang>

C++

include <iostream>
include <sstream>
include <iterator>
include <vector>
include <math.h>

using namespace std;

class fractran { public:

   void run( std::string p, int s, int l  )
   {
       start = s; limit = l;
       istringstream iss( p ); vector<string> tmp;
       copy( istream_iterator<string>( iss ), istream_iterator<string>(), back_inserter<vector<string> >( tmp ) );

       string item; vector< pair<float, float> > v;

pair<float, float> a; for( vector<string>::iterator i = tmp.begin(); i != tmp.end(); i++ ) { string::size_type pos = ( *i ).find( '/', 0 ); if( pos != std::string::npos ) { a = make_pair( atof( ( ( *i ).substr( 0, pos ) ).c_str() ), atof( ( ( *i ).substr( pos + 1 ) ).c_str() ) ); v.push_back( a ); } }

exec( &v );

private:

   void exec( vector< pair<float, float> >* v )
   {

int cnt = 0; bool found; float r; while( cnt < limit ) { cout << cnt << " : " << start << "\n"; cnt++; vector< pair<float, float> >::iterator it = v->begin(); found = false; while( it != v->end() ) { r = start * ( ( *it ).first / ( *it ).second ); if( r == floor( r ) ) { found = true; break; } ++it; }

if( found ) start = ( int )r; else break; }

   }
   int start, limit;

}; int main( int argc, char* argv[] ) {

   fractran f; f.run( "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 );
   return system( "pause" );

} </lang>

Output:

Common Lisp

<lang lisp>(defun fractran (n frac-list)

 (lambda ()
   (prog1
     n
     (when n
       (let ((f (find-if (lambda (frac)
                           (integerp (* n frac)))
                         frac-list)))
         (when f (setf n (* f n))))))))

test

(defvar *primes-ft* '(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))

(loop with fractran-instance = (fractran 2 *primes-ft*)

     repeat 20
     for next = (funcall fractran-instance)
     until (null next)
     do (print next))</lang>

Output:

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:

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]

Go

Basic task: This compiles to produce a program that reads the limit, starting number n, and list of fractions as command line arguments, with the list of fractions as a single argument. <lang go>package main

import (

   "fmt"
   "log"
   "math/big"
   "os"
   "strconv"
   "strings"

)

func compile(src string) ([]big.Rat, bool) {

   s := strings.Fields(src)
   r := make([]big.Rat, len(s))
   for i, s1 := range s {
       if _, ok := r[i].SetString(s1); !ok {
           return nil, false
       }
   }
   return r, true

}

func exec(p []big.Rat, n *big.Int, limit int) {

   var q, r big.Int

rule:

   for i := 0; i < limit; i++ {
       fmt.Printf("%d ", n)
       for j := range p {
           q.QuoRem(n, p[j].Denom(), &r)
           if r.BitLen() == 0 {
               n.Mul(&q, p[j].Num())
               continue rule
           }
       }
       break
   }
   fmt.Println()

}

func usage() {

   log.Fatal("usage: ft <limit> <n> <prog>")

}

func main() {

   if len(os.Args) != 4 {
       usage()
   }
   limit, err := strconv.Atoi(os.Args[1])
   if err != nil {
       usage()
   }
   var n big.Int
   _, ok := n.SetString(os.Args[2], 10)
   _, ok := n.SetString(os.Args[2], 10)
   if !ok {
       usage()
   }
   p, ok := compile(os.Args[3])
   if !ok {
       usage()
   }
   exec(p, &n, limit)

}</lang>

Command line usage, with program compiled as "ft":

> ft 15 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"
2 15 825 725 1925 2275 425 390 330 290 770 910 170 156 132

Extra credit: This invokes above program with appropriate arguments, and processes the output to obtain the 20 primes. <lang go>package main

import (

   "fmt"
   "log"
   "math/big"
   "os"
   "os/exec"

)

func main() {

   c := exec.Command("ft", "1000000", "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`)
   c.Stderr = os.Stderr
   r, err := c.StdoutPipe()
   if err != nil {
       log.Fatal(err)
   }
   if err = c.Start(); err != nil {
       log.Fatal(err)
   }
   var n big.Int
   for primes := 0; primes < 20; {
       if _, err = fmt.Fscan(r, &n); err != nil {
           log.Fatal(err)
       }
       l := n.BitLen() - 1
       n.SetBit(&n, l, 0)
       if n.BitLen() == 0 && l > 1 {
           fmt.Printf("%d ", l)
           primes++
       }
   }
   fmt.Println()

}</lang>

Output:

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71

Haskell

<lang haskell>import Data.List (find) import Data.Ratio (Ratio, (%), denominator)

fractran :: (Integral a) => [Ratio a] -> a -> [a] fractran fracts n = n :

 case find (\f -> n `mod` denominator f == 0) fracts of
   Nothing -> []
   Just f -> fractran fracts $ truncate (fromIntegral n * f)

main :: IO () main = print $ take 15 $ 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</lang>

Output:

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

Icon and Unicon

Works in both languages:

<lang unicon>record fract(n,d)

procedure main(A)

   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)

end

procedure fractran(s, n, limit)

   execute(parse(s),n, limit)

end

procedure parse(s)

   f := []
   s ? while not pos(0) do {
           tab(upto(' ')|0) ? put(f,fract(tab(upto('/')), (move(1),tab(0))))
           move(1)
           }
   return f

end

procedure execute(f,d,limit)

    /limit := 15
    every !limit do {
        if d := (d%f[i := !*f].d == 0, (writes(" ",d)/f[i].d)*f[i].n) then {}
        else break write()
        }
    write()

end</lang>

Output:

->fractan
 2 15 825 725 1925 2275 425 390 330 290 770 910 170 156 132
->

J

Solution: <lang j>toFrac=: '/r' 0&".@charsub ] NB. read fractions from string fractran15=: ({~ (= <.) i. 1:)@(toFrac@[ * ]) ^:(<15) NB. return first 15 Fractran results</lang>

Example: <lang j> taskstr=: '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'

  taskstr fractran15 2

2 15 825 725 1925 2275 425 390 330 290 770 910 170 156 132</lang>

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

Works with: rakudo version 2014-01-23

A Fractran program potentially returns an infinite list, and infinite lists are a common data structure in Perl 6. The limit is therefore enforced only by slicing the infinite list. <lang perl6>sub ft (\n) {

   first Int, map (* * n).narrow,
       <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>, 0

} constant FT = 2, &ft ... 0; say FT[^100];</lang>

Output:

2 15 825 725 1925 2275 425 390 330 290 770 910 170 156 132 116 308 364 68 4 30 225 12375 10875 28875 25375 67375 79625 14875 13650 2550 2340 1980 1740 4620 4060 10780 12740 2380 2184 408 152 92 380 230 950 575 2375 9625 11375 2125 1950 1650 1450 3850 4550 850 780 660 580 1540 1820 340 312 264 232 616 728 136 8 60 450 3375 185625 163125 433125 380625 1010625 888125 2358125 2786875 520625 477750 89250 81900 15300 14040 11880 10440 27720 24360 64680 56840 150920 178360 33320 30576 5712 2128 1288

Extra credit:

We can weed out all the powers of two into another infinite constant list based on the first list. In this case the sequence is limited only by our patience, and a ^C from the terminal. The .msb method finds the most significant bit of an integer, which conveniently is the base-2 log of the power-of-two in question. <lang perl6>constant FT2 = FT.grep: { not $_ +& ($_ - 1) } for 1..* -> $i {

   given FT2[$i] {
       say $i, "\t", .msb, "\t", $_;
   }

}</lang>

Output:

1	2	4
2	3	8
3	5	32
4	7	128
5	11	2048
6	13	8192
7	17	131072
8	19	524288
9	23	8388608
10	29	536870912
11	31	2147483648
12	37	137438953472
13	41	2199023255552
14	43	8796093022208
15	47	140737488355328
16	53	9007199254740992
17	59	576460752303423488
18	61	2305843009213693952
19	67	147573952589676412928
20	71	2361183241434822606848
^C

Python

Python: Generate series from a fractran program

<lang python>from fractions import Fraction

def fractran(n, fstring='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'):
   flist = [Fraction(f) for f in fstring.replace(' ', ).split(',')]

   n = Fraction(n)
   while True:
       yield n.numerator
       for f in flist:
           if (n * f).denominator == 1:
               break
       else:
           break
       n *= f

if __name__ == '__main__':

   n, m = 2, 15
   print('First %i members of fractran(%i):\n  ' % (m, n) +
         ', '.join(str(f) for f,i in zip(fractran(n), range(m))))</lang>

Output:

First 15 members of fractran(2):
  2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132

Python: Generate primes

Use fractran above as a module imported into the following program.

<lang python> from fractran import fractran

def fractran_primes():

   for i, fr in enumerate(fractran(2), 1):
       binstr = bin(fr)[2:]
       if binstr.count('1') == 1:
           prime = binstr.count('0')
           if prime > 1:   # Skip 2**0 and 2**1
               yield prime, i

if __name__ == '__main__':

   for (prime, i), j in zip(fractran_primes(), range(15)):
       print("Generated prime %2i from the %6i'th member of the fractran series" % (prime, i))</lang>

Output:

Generated prime  2 from the     20'th member of the fractran series
Generated prime  3 from the     70'th member of the fractran series
Generated prime  5 from the    281'th member of the fractran series
Generated prime  7 from the    708'th member of the fractran series
Generated prime 11 from the   2364'th member of the fractran series
Generated prime 13 from the   3877'th member of the fractran series
Generated prime 17 from the   8069'th member of the fractran series
Generated prime 19 from the  11320'th member of the fractran series
Generated prime 23 from the  19202'th member of the fractran series
Generated prime 29 from the  36867'th member of the fractran series
Generated prime 31 from the  45552'th member of the fractran series
Generated prime 37 from the  75225'th member of the fractran series
Generated prime 41 from the 101113'th member of the fractran series
Generated prime 43 from the 117832'th member of the fractran series
Generated prime 47 from the 152026'th member of the fractran series

Racket

Translation of: D

Simple version, without sequences.

<lang Racket>#lang racket

(define (displaysp x)

 (display x)
 (display " "))

(define (read-string-list str)

 (map string->number
      (string-split (string-replace str " " "") ",")))

(define (eval-fractran n list)

 (for/or ([e (in-list list)])
   (let ([en (* e n)])
     (and (integer? en) en))))

(define (show-fractran fr n s)

 (printf "First ~a members of fractran(~a):\n" s n)
 (displaysp n) 
 (for/fold ([n n]) ([i (in-range (- s 1))])
   (let ([new-n (eval-fractran n fr)])
     (displaysp new-n) 
     new-n))
 (void))

(define fractran

 (read-string-list 
  (string-append "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")))

(show-fractran fractran 2 15)</lang>

Output:

First 15 members of fractran(2):
2 15 825 725 1925 2275 425 390 330 290 770 910 170 156 132

REXX

Programming note: extra blanks can be inserted in the fractions before and/or after the solidus [/].

showing all terms

<lang rexx>/*REXX pgm runs FRACTRAN for a given set of fractions and from a given N*/ numeric digits 999 /*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 terms==|terms==',' then terms=100 /*TERMS specified? 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=space(fracs,0) /* [↑] use default for fractions.*/

                do i=1  while f\==;    parse var f n.i '/' d.i ',' f
                end   /*i*/           /* [↑]   parse all the fractions.*/

=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.*/ say terms ' terms are being shown:' /*display a kind of header/title.*/

   do j=1  for  terms                 /*perform loop once for each term*/
      do k=1  for  #;  if N//d.k\==0  then iterate    /*not an integer?*/
      say right('term' j,35) '──► ' N /*display the Nth term  with  N. */
      N = N   %  d.k  *  n.k          /*calculate the next term (use %)*/
      leave                           /*go start calculating next term.*/
      end   /*k*/                     /* [↑]  if integer, found a new N*/
   end      /*j*/
                                      /*stick a fork in it, we're done.*/</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 are being shown:
                             term 1 ──►  2
                             term 2 ──►  15
                             term 3 ──►  825
                             term 4 ──►  725
                             term 5 ──►  1925
                             term 6 ──►  2275
                             term 7 ──►  425
                             term 8 ──►  390
                             term 9 ──►  330
                            term 10 ──►  290
                            term 11 ──►  770
                            term 12 ──►  910
                            term 13 ──►  170
                            term 14 ──►  156
                            term 15 ──►  132
                            term 16 ──►  116
                            term 17 ──►  308
                            term 18 ──►  364
                            term 19 ──►  68
                            term 20 ──►  4
                            term 21 ──►  30
                            term 22 ──►  225
                            term 23 ──►  12375
                            term 24 ──►  10875
                            term 25 ──►  28875
                            term 26 ──►  25375
                            term 27 ──►  67375
                            term 28 ──►  79625
                            term 29 ──►  14875
                            term 30 ──►  13650
                            term 31 ──►  2550
                            term 32 ──►  2340
                            term 33 ──►  1980
                            term 34 ──►  1740
                            term 35 ──►  4620
                            term 36 ──►  4060
                            term 37 ──►  10780
                            term 38 ──►  12740
                            term 39 ──►  2380
                            term 40 ──►  2184
                            term 41 ──►  408
                            term 42 ──►  152
                            term 43 ──►  92
                            term 44 ──►  380
                            term 45 ──►  230
                            term 46 ──►  950
                            term 47 ──►  575
                            term 48 ──►  2375
                            term 49 ──►  9625
                            term 50 ──►  11375
                            term 51 ──►  2125
                            term 52 ──►  1950
                            term 53 ──►  1650
                            term 54 ──►  1450
                            term 55 ──►  3850
                            term 56 ──►  4550
                            term 57 ──►  850
                            term 58 ──►  780
                            term 59 ──►  660
                            term 60 ──►  580
                            term 61 ──►  1540
                            term 62 ──►  1820
                            term 63 ──►  340
                            term 64 ──►  312
                            term 65 ──►  264
                            term 66 ──►  232
                            term 67 ──►  616
                            term 68 ──►  728
                            term 69 ──►  136
                            term 70 ──►  8
                            term 71 ──►  60
                            term 72 ──►  450
                            term 73 ──►  3375
                            term 74 ──►  185625
                            term 75 ──►  163125
                            term 76 ──►  433125
                            term 77 ──►  380625
                            term 78 ──►  1010625
                            term 79 ──►  888125
                            term 80 ──►  2358125
                            term 81 ──►  2786875
                            term 82 ──►  520625
                            term 83 ──►  477750
                            term 84 ──►  89250
                            term 85 ──►  81900
                            term 86 ──►  15300
                            term 87 ──►  14040
                            term 88 ──►  11880
                            term 89 ──►  10440
                            term 90 ──►  27720
                            term 91 ──►  24360
                            term 92 ──►  64680
                            term 93 ──►  56840
                            term 94 ──►  150920
                            term 95 ──►  178360
                            term 96 ──►  33320
                            term 97 ──►  30576
                            term 98 ──►  5712
                            term 99 ──►  2128
                           term 100 ──►  1288

showing prime numbers

Programming note: If the number of terms specified (the 2^nd argument) is negative, then only powers of two are displayed. <lang rexx>/*REXX pgm runs FRACTRAN for a given set of fractions and from a given N*/ numeric digits 999; w=length(digits()) /*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 terms==|terms==',' then terms=100 /*TERMS specified? 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=space(fracs,0) /* [↑] use default for fractions.*/ L=length(N) /*length in decimal digits of N.*/ tell= terms>0 /*flag: show # or a power of 2.*/

                do i=1  while f\==;    parse var f n.i '/' d.i ',' f
                end   /*i*/           /* [↑]   parse all the fractions.*/

!.=0 /*default value for powers of 2.*/ if \tell then do p=0 until length(_)>digits(); _=2**p; !._=1

              if p<2  then @._=left(,w+9)          '2**'left(p,w)   " "
                      else @._='(prime' right(p,w)")  2**"left(p,w)   ' '
              end   /*p*/             /* [↑]  build powers of 2 tables.*/

=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 tell then say terms ' terms are being shown:' /*display hdr.*/

        else say 'only powers of two are being shown:'   /*   "     "  */

q='(max digits used: ' /*a literal used in the SAY below*/

 do j=1  for  abs(terms)              /*perform loop once for each term*/
    do k=1  for  #;  if N//d.k\==0  then iterate      /*not an integer?*/
    if tell then say right('term' j,35) '──► ' N   /*display Nth term&N*/
            else if !.N  then say right('term' j,15) '──►' @.N q,
                                  right(L,w)")  "       N         /*2ⁿ.*/
    N = N   %  d.k  *  n.k            /*calculate the next term (use %)*/
    L=max(L, length(N))               /*maximum number of decimal digs.*/
    leave                             /*go start calculating next term.*/
    end   /*k*/                       /* [↑]  if integer, found a new N*/
 end      /*j*/
                                      /*stick a fork in it, we're done.*/</lang>

output using the input of: , -50000000
(fifty million)

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
only powers of two are being shown:
         term 1                  2**1     (max digits used:   1)   2
        term 20 ──► (prime   2)  2**2     (max digits used:   4)   4
        term 70 ──► (prime   3)  2**3     (max digits used:   5)   8
       term 281 ──► (prime   5)  2**5     (max digits used:   8)   32
       term 708 ──► (prime   7)  2**7     (max digits used:  12)   128
      term 2364 ──► (prime  11)  2**11    (max digits used:  18)   2048
      term 3877 ──► (prime  13)  2**13    (max digits used:  21)   8192
      term 8069 ──► (prime  17)  2**17    (max digits used:  27)   131072
     term 11320 ──► (prime  19)  2**19    (max digits used:  30)   524288
     term 19202 ──► (prime  23)  2**23    (max digits used:  36)   8388608
     term 36867 ──► (prime  29)  2**29    (max digits used:  46)   536870912
     term 45552 ──► (prime  31)  2**31    (max digits used:  49)   2147483648
     term 75225 ──► (prime  37)  2**37    (max digits used:  58)   137438953472
...
 term 193455490 ──► (prime 523)  2**523   (max digits used: 808)   27459190640522438859927603196325572869077741200573221637577853836742172733590624208490238562645818219909185245565923432148487951998866575250296113164460228608

Output note: There are intermediary numbers (not powers of two) that are hundreds of digits long.

Ruby

<lang ruby>str ="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" FractalProgram = str.split(',').map(&:to_r) #=> array of rationals

def run(num)

 return to_enum(__method__, num) unless block_given?
 loop{ yield num *= FractalProgram.detect{|f| (num*f).denominator == 1} }

end

def generate_primes

 return to_enum(__method__) unless block_given?
 run(2).each do |num|
   l = Math.log2(num)
   yield l.to_i if l.floor == l
 end

end

p run(2).take(20)

start = Time.now p generate_primes.take(20) puts "Calculating 20 primes took #{Time.now - start} seconds." </lang>

Output:

[(15/1), (825/1), (725/1), (1925/1), (2275/1), (425/1), (390/1), (330/1), (290/1), (770/1), (910/1), (170/1), (156/1), (132/1), (116/1), (308/1), (364/1), (68/1), (4/1), (30/1)]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]
Calculating 20 primes took 4.654158713 seconds.

Tcl

Works with: Tcl version 8.6

<lang tcl>package require Tcl 8.6

oo::class create Fractran {

   variable fracs nco
   constructor {fractions} {

set fracs {} foreach frac $fractions { if {[regexp {^(\d+)/(\d+),?$} $frac -> num denom]} { lappend fracs $num $denom } else { return -code error "$frac is not a supported fraction" } } if {![llength $fracs]} { return -code error "need at least one fraction" }

   method execute {n {steps 15}} {

set co [coroutine [incr nco] my Generate $n] for {set i 0} {$i < $steps} {incr i} { lappend result [$co] } catch {rename $co ""} return $result

   method Step {n} {

foreach {num den} $fracs { if {$n % $den} continue return [expr {$n * $num / $den}] } return -code break

   }
   method Generate {n} {

yield [info coroutine] while 1 { yield $n set n [my Step $n] } return -code break

}

set ft [Fractran new {

   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

}] puts [$ft execute 2]</lang>

Output:

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

You can just collect powers of 2 by monkey-patching in something like this: <lang tcl>oo::objdefine $ft method pow2 {n} {

   set co [coroutine [incr nco] my Generate 2]
   set pows {}
   while {[llength $pows] < $n} {

set item [$co] if {($item & ($item-1)) == 0} { lappend pows $item }

   }
   return $pows

} puts [$ft pow2 10]</lang> Which will then produce this additional output:

2 4 8 32 128 2048 8192 131072 524288 8388608