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 , together with an initial positive integer input .
The program is run by updating the integer as follows:
- for the first fraction, , in the list for which is an integer, replace by ;
- repeat this rule until no fraction in the list produces an integer when multiplied by , then halt.
Conway gave a program for primes in FRACTRAN:
- , , , , , , , , , , , , ,
Starting with , this FRACTRAN program will change in , then , generating the following sequence of integers:
- , , , , , , , , , , ,
After 2, this sequence contains the following powers of 2:
- , , , , , , , ,
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 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.
- 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.
- Number Pathology: Fractran by Mark C. Chu-Carroll; October 27, 2006.
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:
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
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++
<lang cpp>
- 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:
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
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:
2 15 825 725 1925 2275 425 390 330 290 770 910 170 156 132 116 308 364 68 4
D
Simple Version
<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]
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 ->
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. 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
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 2nd 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 101113 ──► (prime 41) 2**41 (max digits used: 64) 2199023255552
term 117832 ──► (prime 43) 2**43 (max digits used: 67) 8796093022208
term 152026 ──► (prime 47) 2**47 (max digits used: 73) 140737488355328
term 215385 ──► (prime 53) 2**53 (max digits used: 83) 9007199254740992
term 293376 ──► (prime 59) 2**59 (max digits used: 92) 576460752303423488
term 327021 ──► (prime 61) 2**61 (max digits used: 95) 2305843009213693952
term 428554 ──► (prime 67) 2**67 (max digits used: 104) 147573952589676412928
term 507520 ──► (prime 71) 2**71 (max digits used: 110) 2361183241434822606848
term 555695 ──► (prime 73) 2**73 (max digits used: 113) 9444732965739290427392
term 700064 ──► (prime 79) 2**79 (max digits used: 123) 604462909807314587353088
term 808332 ──► (prime 83) 2**83 (max digits used: 129) 9671406556917033397649408
term 989527 ──► (prime 89) 2**89 (max digits used: 138) 618970019642690137449562112
term 1273491 ──► (prime 97) 2**97 (max digits used: 151) 158456325028528675187087900672
term 1434367 ──► (prime 101) 2**101 (max digits used: 157) 2535301200456458802993406410752
term 1530214 ──► (prime 103) 2**103 (max digits used: 160) 10141204801825835211973625643008
term 1710924 ──► (prime 107) 2**107 (max digits used: 166) 162259276829213363391578010288128
term 1818255 ──► (prime 109) 2**109 (max digits used: 169) 649037107316853453566312041152512
term 2019963 ──► (prime 113) 2**113 (max digits used: 175) 10384593717069655257060992658440192
term 2833090 ──► (prime 127) 2**127 (max digits used: 197) 170141183460469231731687303715884105728
term 3104686 ──► (prime 131) 2**131 (max digits used: 203) 2722258935367507707706996859454145691648
term 3546321 ──► (prime 137) 2**137 (max digits used: 212) 174224571863520493293247799005065324265472
term 3720786 ──► (prime 139) 2**139 (max digits used: 215) 696898287454081973172991196020261297061888
term 4549719 ──► (prime 149) 2**149 (max digits used: 231) 713623846352979940529142984724747568191373312
term 4755582 ──► (prime 151) 2**151 (max digits used: 234) 2854495385411919762116571938898990272765493248
term 5329875 ──► (prime 157) 2**157 (max digits used: 243) 182687704666362864775460604089535377456991567872
term 5958404 ──► (prime 163) 2**163 (max digits used: 252) 11692013098647223345629478661730264157247460343808
term 6400898 ──► (prime 167) 2**167 (max digits used: 259) 187072209578355573530071658587684226515959365500928
term 7120509 ──► (prime 173) 2**173 (max digits used: 268) 11972621413014756705924586149611790497021399392059392
term 7868448 ──► (prime 179) 2**179 (max digits used: 277) 766247770432944429179173513575154591809369561091801088
term 8164153 ──► (prime 181) 2**181 (max digits used: 280) 3064991081731777716716694054300618367237478244367204352
term 9541986 ──► (prime 191) 2**191 (max digits used: 296) 3138550867693340381917894711603833208051177722232017256448
term 9878163 ──► (prime 193) 2**193 (max digits used: 299) 12554203470773361527671578846415332832204710888928069025792
term 10494775 ──► (prime 197) 2**197 (max digits used: 305) 200867255532373784442745261542645325315275374222849104412672
term 10852158 ──► (prime 199) 2**199 (max digits used: 308) 803469022129495137770981046170581301261101496891396417650688
term 12871594 ──► (prime 211) 2**211 (max digits used: 327) 3291009114642412084309938365114701009965471731267159726697218048
term 15137114 ──► (prime 223) 2**223 (max digits used: 345) 13479973333575319897333507543509815336818572211270286240551805124608
term 15956646 ──► (prime 227) 2**227 (max digits used: 351) 215679573337205118357336120696157045389097155380324579848828881993728
term 16429799 ──► (prime 229) 2**229 (max digits used: 354) 862718293348820473429344482784628181556388621521298319395315527974912
term 17293373 ──► (prime 233) 2**233 (max digits used: 361) 13803492693581127574869511724554050904902217944340773110325048447598592
term 18633402 ──► (prime 239) 2**239 (max digits used: 370) 883423532389192164791648750371459257913741948437809479060803100646309888
term 19157411 ──► (prime 241) 2**241 (max digits used: 373) 3533694129556768659166595001485837031654967793751237916243212402585239552
term 21564310 ──► (prime 251) 2**251 (max digits used: 388) 3618502788666131106986593281521497120414687020801267626233049500247285301248
term 23157731 ──► (prime 257) 2**257 (max digits used: 398) 231584178474632390847141970017375815706539969331281128078915168015826259279872
term 24805778 ──► (prime 263) 2**263 (max digits used: 407) 14821387422376473014217086081112052205218558037201992197050570753012880593911808
term 26506125 ──► (prime 269) 2**269 (max digits used: 416) 948568795032094272909893509191171341133987714380927500611236528192824358010355712
term 27168588 ──► (prime 271) 2**271 (max digits used: 419) 3794275180128377091639574036764685364535950857523710002444946112771297432041422848
term 28973145 ──► (prime 277) 2**277 (max digits used: 428) 242833611528216133864932738352939863330300854881517440156476551217363035650651062272
term 30230537 ──► (prime 281) 2**281 (max digits used: 435) 3885337784451458141838923813647037813284813678104279042503624819477808570410416996352
term 30952920 ──► (prime 283) 2**283 (max digits used: 438) 15541351137805832567355695254588151253139254712417116170014499277911234281641667985408
term 34284307 ──► (prime 293) 2**293 (max digits used: 453) 15914343565113172548972231940698266883214596825515126958094847260581103904401068017057792
term 39303996 ──► (prime 307) 2**307 (max digits used: 475) 260740604970814219042361048116400404614587954389239840081425977517360806369707098391474864128
term 40844960 ──► (prime 311) 2**311 (max digits used: 481) 4171849679533027504677776769862406473833407270227837441302815640277772901915313574263597826048
term 41728501 ──► (prime 313) 2**313 (max digits used: 484) 16687398718132110018711107079449625895333629080911349765211262561111091607661254297054391304192
term 43329639 ──► (prime 317) 2**317 (max digits used: 490) 266998379490113760299377713271194014325338065294581596243380200977777465722580068752870260867072
term 49260306 ──► (prime 331) 2**331 (max digits used: 512) 4374501449566023848745004454235242730706338861786424872851541212819905998398751846447026354046107648
term 51937081 ──► (prime 337) 2**337 (max digits used: 521) 279968092772225526319680285071055534765205687154331191862498637620473983897520118172609686658950889472
term 56604582 ──► (prime 347) 2**347 (max digits used: 537) 286687326998758938951352611912760867599570623646035140467198604923365359511060601008752319138765710819328
term 57702885 ──► (prime 349) 2**349 (max digits used: 540) 1146749307995035755805410447651043470398282494584140561868794419693461438044242404035009276555062843277312
term 59689265 ──► (prime 353) 2**353 (max digits used: 546) 18347988927920572092886567162416695526372519913346248989900710715095383008707878464560148424881005492436992
term 62727632 ──► (prime 359) 2**359 (max digits used: 555) 1174271291386916613944740298394668513687841274454159935353645485766104512557304221731849499192384351515967488
term 67038338 ──► (prime 367) 2**367 (max digits used: 567) 300613450595050653169853516389035139504087366260264943450533244356122755214669880763353471793250393988087676928
term 70368163 ──► (prime 373) 2**373 (max digits used: 577) 19239260838083241802870625048898248928261591440656956380834127638791856333738872368854622194768025215237611323392
term 73863194 ──► (prime 379) 2**379 (max digits used: 586) 1231312693637327475383720003129487931408741852202045208373384168882678805359287831606695820465153613775207124697088
term 76202274 ──► (prime 383) 2**383 (max digits used: 592) 19701003098197239606139520050071806902539869635232723333974146702122860885748605305707133127442457820403313995153408
term 79772347 ──► (prime 389) 2**389 (max digits used: 601) 1260864198284623334792929283204595641762551656654894293374345388935863096687910739565256520156317300505812095689818112
term 84816569 ──► (prime 397) 2**397 (max digits used: 614) 322781234760863573706989896500376484291213224103652939103832419567580952752105149328705669160017228929487896496593436672
term 87381117 ──► (prime 401) 2**401 (max digits used: 620) 5164499756173817179311838344006023748659411585658447025661318713081295244033682389259290706560275662871806343945494986752
term 92828325 ──► (prime 409) 2**409 (max digits used: 632) 1322111937580497197903830616065542079656809365928562438569297590548811582472622691650378420879430569695182424050046716608512
term 99545926 ──► (prime 419) 2**419 (max digits used: 648) 1353842624082429130653522550851115089568572790710847937094960732721983060451965636249987502980536903367866802227247837807116288
term 101143801 ──► (prime 421) 2**421 (max digits used: 651) 5415370496329716522614090203404460358274291162843391748379842930887932241807862544999950011922147613471467208908991351228465152
term 108255790 ──► (prime 431) 2**431 (max digits used: 666) 5545339388241629719156828368286167406872874150751633150340959161229242615611251246079948812208279156194782421922807143657948315648
term 109945989 ──► (prime 433) 2**433 (max digits used: 669) 22181357552966518876627313473144669627491496603006532601363836644916970462445004984319795248833116624779129687691228574631793262592
term 114668940 ──► (prime 439) 2**439 (max digits used: 679) 1419606883389857208104148062281258856159455782592418086487285545274686109596480318996466895925319463985864300012238628776434768805888
term 117799872 ──► (prime 443) 2**443 (max digits used: 685) 22713710134237715329666368996500141698551292521478689383796568724394977753543685103943470334805111423773828800195818060422956300894208
term 122561883 ──► (prime 449) 2**449 (max digits used: 694) 1453677448591213781098647615776009068707282721374636120562980398361278576226795846652382101427527131121525043212532355867069203257229312
term 129218645 ──► (prime 457) 2**457 (max digits used: 706) 372141426839350727961253789638658321589064376671906846864122981980487315514059736743009817965446945567110411062408283101969716033850703872
term 132609591 ──► (prime 461) 2**461 (max digits used: 713) 5954262829429611647380060634218533145425030026750509549825967711687797048224955787888157087447151129073766576998532529631515456541611261952
term 134541964 ──► (prime 463) 2**463 (max digits used: 716) 23817051317718446589520242536874132581700120107002038199303870846751188192899823151552628349788604516295066307994130118526061826166445047808
term 138021884 ──► (prime 467) 2**467 (max digits used: 722) 381072821083495145432323880589986121307201921712032611188861933548019011086397170424842053596617672260721060927906081896416989218663120764928
term 148683320 ──► (prime 479) 2**479 (max digits used: 740) 1560874275157996115690798614896583152874299071332485575429578479812685869409882810060153051531745985579913465560703311447723987839644142653145088
term 156267926 ──► (prime 487) 2**487 (max digits used: 753) 399583814440447005616844445413525287135820562261116307309972090832047582568929999375399181192126972308457847183540047730617340886948900519205142528
term 160115280 ──► (prime 491) 2**491 (max digits used: 759) 6393341031047152089869511126616404594173128996177860916959553453312761321102879990006386899074031556935325554936640763689877454191182408307282280448
term 168192150 ──► (prime 499) 2**499 (max digits used: 771) 1636695303948070935006594848413799576108321023021532394741645684048066898202337277441635046162952078575443342063780035504608628272942696526664263794688
term 172230120 ──► (prime 503) 2**503 (max digits used: 777) 26187124863169134960105517574620793217733136368344518315866330944769070371237396439066160738607233257207093473020480568073738052367083144426628220715008
term 178355439 ──► (prime 509) 2**509 (max digits used: 787) 1675975991242824637446753124775730765934920727574049172215445180465220503759193372100234287270862928461253982273310756356719235351493321243304206125760512
term 190990159 ──► (prime 521) 2**521 (max digits used: 805) 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057152
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.
Tcl
<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