Anonymous user
Fractran: Difference between revisions
Adding C#.
(→{{header|JavaScript}}: Added a functionally composed version, attempting primes, but lacking bigInt) |
imported>JacobNoel (Adding C#.) |
||
| (84 intermediate revisions by 23 users not shown) | |||
Line 1:
{{task|Prime Numbers}}
'''[[wp:FRACTRAN|FRACTRAN]]''' is a Turing-complete esoteric programming language invented by the mathematician [[wp:John Horton Conway|John Horton Conway]].
Line 46:
* [http://scienceblogs.com/goodmath/2006/10/27/prime-number-pathology-fractra/Prime Number Pathology: Fractran] by Mark C. Chu-Carroll; October 27, 2006.
<br><br>
=={{header|11l}}==
{{trans|D}}
<syntaxhighlight lang="11l">F fractran(prog, =val, limit)
V fracts = prog.split(‘ ’).map(p -> p.split(‘/’).map(i -> Int(i)))
[Float] r
L(n) 0 .< limit
r [+]= val
L(p) fracts
I val % p[1] == 0
val = p[0] * val / p[1]
L.break
R r
print(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))</syntaxhighlight>
{{out}}
<pre>
[2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132]
</pre>
=={{header|360 Assembly}}==
<syntaxhighlight lang="360asm">* FRACTRAN 17/02/2019
FRACTRAN CSECT
USING FRACTRAN,R13 base register
B 72(R15) skip savearea
DC 17F'0' savearea
SAVE (14,12) save previous context
ST R13,4(R15) link backward
ST R15,8(R13) link forward
LR R13,R15 set addressability
LA R6,1 i=1
DO WHILE=(C,R6,LE,TERMS) do i=1 to terms
LA R7,1 j=1
DO WHILE=(C,R7,LE,=A(NF)) do j=1 to nfracs
LR R1,R7 j
SLA R1,3 ~
L R2,FRACS-4(R1) d(j)
L R4,NN nn
SRDA R4,32 ~
DR R4,R2 nn/d(j)
IF LTR,R4,Z,R4 THEN if mod(nn,d(j))=0 then
XDECO R6,XDEC edit i
MVC PG(3),XDEC+9 output i
L R1,NN nn
XDECO R1,PG+5 edit & output nn
XPRNT PG,L'PG print buffer
LR R1,R7 j
SLA R1,3 ~
L R3,FRACS-8(R1) n(j)
MR R4,R3 *n(j)
ST R5,NN nn=nn/d(j)*n(j)
B LEAVEJ leave j
ENDIF , end if
LA R7,1(R7) j++
ENDDO , end do j
LEAVEJ LA R6,1(R6) i++
ENDDO , end do i
L R13,4(0,R13) restore previous savearea pointer
RETURN (14,12),RC=0 restore registers from calling sav
NF EQU (TERMS-FRACS)/8 number of fracs
NN DC F'2' nn
FRACS DC F'17',F'91',F'78',F'85',F'19',F'51',F'23',F'38',F'29',F'33'
DC F'77',F'29',F'95',F'23',F'77',F'19',F'1',F'17',F'11',F'13'
DC F'13',F'11',F'15',F'14',F'15',F'2',F'55',F'1'
TERMS DC F'100' terms
PG DC CL80'*** :' buffer
XDEC DS CL12 temp
REGEQU
END FRACTRAN</syntaxhighlight>
{{out}}
<pre>
1 : 2
2 : 15
3 : 825
4 : 725
5 : 1925
6 : 2275
7 : 425
8 : 390
9 : 330
10 : 290
...
99 : 2128
100 : 1288
</pre>
=={{header|Ada}}==
<
procedure Fractan is
Line 91 ⟶ 178:
2, 15);
-- output is "0: 2 1: 15 2: 825 3: 725 ... 14: 132 15: 116"
end Fractan;</
{{out}}
Line 98 ⟶ 185:
=={{header|ALGOL 68}}==
{{works with|ALGOL 68G|Any - tested with release 2.8.win32}}
<
# we use Algol 68G's LONG LONG INT with a precision of 100 digits #
PR precision 100 PR
Line 171 ⟶ 258:
print( ( whole( pos, -12 ) + " " + whole( power of 2, -6 ) + " (" + whole( n OF pf, 0 ) + ")", newline ) )
FI
OD</
{{out}}
<pre>
Line 197 ⟶ 284:
507519 71 (2361183241434822606848)
</pre>
=={{header|APL}}==
{{works with|Dyalog APL}}
<syntaxhighlight lang="apl">fractran←{
parts ← ' '∘≠⊆⊢
frac ← ⍎¨'/'∘≠⊆⊢
simp ← ⊢÷∨/
mul ← simp×
prog ← simp∘frac¨parts ⍺
step ← {⊃⊃(1=2⊃¨next)/next←⍺ mul¨⊂(⍵ 1)}
(start nstep)←⍵
rslt ← ⊃(⊢,⍨prog∘step∘⊃)⍣nstep¨start
⌽(⊢(/⍨)(∨\0∘≠))rslt
}</syntaxhighlight>
{{out}}
<syntaxhighlight lang="apl"> '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' fractran 2 20
2 15 825 725 1925 2275 425 390 330 290 770 910 170 156 132 116 308 364 68 4 30</syntaxhighlight>
=={{header|AutoHotkey}}==
<
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"
Line 222 ⟶ 326:
}
break
}</
{{out}}
<pre>0: 2
Line 247 ⟶ 351:
the "factor" command allows one to decrypt the data. For example, the program below computes the product of a and b, entered as 2<sup>a</sup> and 3<sup>b</sup>, the product being 5<sup>a×b</sup>. Two arrays are computed from the fractions, ns for the numerators and ds for the denominators. Then, every time where the multiplication by a fraction yields an integer, the output of the division is stored into a csv file in factored format.
<
program="1/1 455/33 11/13 1/11 3/7 11/2 1/3"
echo $program | tr " " "\n" | cut -d"/" -f1 | tr "\n" " " > "data"
Line 266 ⟶ 370:
let "t=$t+1"
done
</syntaxhighlight>
If at the beginning n=72=2<sup>3</sup>×3<sup>2</sup> (to compute 3×2), the steps of the computation look like this:
Line 301 ⟶ 405:
This file can be opened with a spreadsheet to draw the successive states of the prime numbers (with countif) and then look how the computation is done in successive steps.
=={{header|Batch File}}==
<
setlocal enabledelayedexpansion
Line 359 ⟶ 462:
echo.
pause
exit /b 1</
{{Out}}
<pre>Input:
Line 393 ⟶ 496:
Note that in some interpreters you may need to press <Return> twice after entering the fractions if the ''Starting value'' prompt doesn't at first appear.
<
v"Starting value: "_^#-*84~p6p00+1<
>:#,_&0" :snoitaretI">:#,_#@>>$&\:v
:$_\:10g5g*:10g6g%v1:\1$\$<|!:-1\.<
g0^<!:-1\p01+1g01$_10g6g/\^>\010p00</
{{out}}
Line 405 ⟶ 508:
Iterations: 16
2 15 825 725 1925 2275 425 390 330 290 770 910 170 156 132 116</pre>
=={{header|BQN}}==
The function <code>RunFractran</code> runs a fractran program, given max iterations on the left, and input, program string on the right. It returns a list of generated numbers.
<code>Fractran</code> performs a single iteration of fractran on a given input, list of numerators and list of denominators.
<syntaxhighlight lang="bqn"># Fractran interpreter
# Helpers
_while_ ← {𝔽⍟𝔾∘𝔽_𝕣_𝔾∘𝔽⍟𝔾𝕩}
ToInt ← 10⊸×⊸+˜´·⌽-⟜'0'
ToFrac ← {
i ← ⊑/'/'=𝕩
ToInt¨i(↑⋈1⊸+⊸↓)𝕩
}
Split ← ((¬-˜⊢×·+`»⊸>)∘≠⊔⊢)
Fractran ← {
𝕊 n‿num‿den:
ind ← ⊑/0=den|num×n
⟨(n×ind⊑num)÷ind⊑den ⋄ num ⋄ den⟩
}
RunFractran ← {
steps 𝕊 inp‿prg:
num‿den ← <˘⍉>ToFrac¨' 'Split prg
step ← 1
list ← ⟨inp⟩
{
step +↩ 1
out ← Fractran 𝕩
list ∾↩ ⊑out
out
} _while_ {𝕊 n‿num‿den: (step<steps)∧ ∨´0=den|num} inp‿num‿den
list
}
seq ← 200 RunFractran 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"
•Out "Generated numbers: "∾•Repr seq
•Out "Primes: "∾•Repr 1↓⌊2⋆⁼(⌈=⌊)∘(2⊸(⋆⁼))⊸/ seq</syntaxhighlight>
<syntaxhighlight lang="text"> )ex fractran.bqn
Generated numbers: 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‿5320‿3220‿13300‿8050‿33250‿20125‿83125‿336875‿398125‿74375‿68250‿12750‿11700‿9900‿8700‿23100‿20300‿53900‿63700‿11900‿10920‿2040‿1872‿1584‿1392‿3696‿3248‿8624‿10192‿1904‿112‿120‿900‿6750‿50625‿2784375‿2446875‿6496875‿5709375‿15159375‿13321875‿35371875‿31084375‿82534375‿97540625‿18221875‿16721250‿3123750‿2866500‿535500‿491400‿91800‿84240‿71280‿62640‿166320‿146160‿388080‿341040‿905520‿795760‿2112880‿2497040‿466480‿428064‿79968‿29792‿18032‿74480‿45080‿186200‿112700‿465500‿281750‿1163750‿704375‿2909375‿11790625‿13934375‿2603125‿2388750‿446250‿409500‿76500‿70200‿59400‿52200‿138600‿121800‿323400‿284200‿754600‿891800‿166600‿152880‿28560‿26208‿4896‿1824‿1104
Primes: 2‿3</syntaxhighlight>
=={{header|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.
<
np n fs A Z fi P p N L M
. !arg:(?N,?n,?fs) {Number of iterations, start n, fractions}
Line 443 ⟶ 590:
str$("\ntime: " flt$(clk$+-1*!t0,4) " sec\n")
, "FRACTRAN.OUT",NEW)
);</
In Linux, run the program as follows (assuming bracmat and the file 'fractran' are in the CWD):
<pre>./bracmat 'get$fractran' &</pre>
Line 479 ⟶ 626:
Using GMP. Powers of two are in brackets.
For extra credit, pipe the output through <code>| less -S</code>.
<
#include <stdlib.h>
#include <gmp.h>
Line 543 ⟶ 690:
return 0;
}</
=={{header|C sharp|C#}}==
The use of <code> using Fractype = (BigInteger numerator, BigInteger denominator);</code> requires C# 12.0.
<syntaxhighlight lang="csharp">
namespace System.Numerics
{
using Fractype = (BigInteger numerator, BigInteger denominator);
struct Quotient
{
private Fractype _frac;
public Fractype Fraction
{
get => _frac;
set => _frac = Reduce(value);
}
public bool IsIntegral => _frac.denominator == 1;
public Quotient(BigInteger num, BigInteger den)
{
Fraction = (num, den);
}
public static BigInteger GCD(BigInteger a, BigInteger b)
{
return (b == 0) ? a : GCD(b, a % b);
}
private static Fractype Reduce(Fractype f)
{
if (f.denominator == 0)
throw new DivideByZeroException();
BigInteger gcd = Quotient.GCD(f.numerator, f.denominator);
return (f.numerator / gcd, f.denominator / gcd);
}
public static Quotient operator *(Quotient a, Quotient b)
=> new Quotient(a._frac.numerator * b._frac.numerator, a._frac.denominator * b._frac.denominator);
public static Quotient operator *(Quotient a, BigInteger n)
=> new Quotient(a._frac.numerator * n, a._frac.denominator);
public static explicit operator Quotient(Fractype t) => new Quotient(t.numerator, t.denominator);
}
class FRACTRAN
{
private Quotient[] code;
public FRACTRAN(Fractype[] _code)
{
code = _code.Select(x => (Quotient) x).ToArray();
}
public (BigInteger value, bool success) Compute(BigInteger n)
{
for (int i = 0; i < code.Length; i++)
if ((code[i] * n).IsIntegral)
return ((code[i] * n).Fraction.numerator, true);
return (0, false);
}
}
class Program
{
public static void Main(string[] args)
{
Fractype[] frac_code = args[0].Split(" ")
.Select(x => ((BigInteger)Int32.Parse(x.Split("/")[0]), (BigInteger)Int32.Parse(x.Split("/")[1].Trim(',')))).ToArray();
BigInteger init = new BigInteger(Int32.Parse(args[1].Trim(',')));
int steps = Int32.Parse(args[2].Trim(','));
FRACTRAN FRACGAME = new FRACTRAN(frac_code);
List<BigInteger> sequence = new List<BigInteger>();
sequence.Add(init);
bool halt = false;
for (int i = 0; i < steps - 1; i++)
{
var k = FRACGAME.Compute(sequence[sequence.Count - 1]);
if (k.success)
sequence.Add(k.value);
else
{
halt = true;
break;
}
}
for (int i = 0; i < sequence.Count; i++)
Console.WriteLine((i + 1).ToString() + ": " + sequence[i]);
if (halt)
Console.WriteLine("HALT");
}
}
}
</syntaxhighlight>
Input:
<code> "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 </code>
Output:
<pre>
1: 2
2: 15
3: 825
4: 725
5: 1925
6: 2275
7: 425
8: 390
9: 330
10: 290
11: 770
12: 910
13: 170
14: 156
15: 132
</pre>
Moreover, modifying the class <code>Program</code> to,
<syntaxhighlight lang="csharp">
class Program
{
private static bool PowerOfTwo(BigInteger b)
{
while (b % 2 == 0)
b /= 2;
return b == 1;
}
private static BigInteger BigLog2(BigInteger b)
{
BigInteger r = 0;
while (b > 1)
{
r++;
b /= 2;
}
return r;
}
public static void Main(string[] args)
{
Fractype[] frac_code = args[0].Split(" ")
.Select(x => ((BigInteger)Int32.Parse(x.Split("/")[0]), (BigInteger)Int32.Parse(x.Split("/")[1].Trim(',')))).ToArray();
BigInteger init = new BigInteger(Int32.Parse(args[1].Trim(',')));
int steps = Int32.Parse(args[2].Trim(','));
FRACTRAN FRACGAME = new FRACTRAN(frac_code);
List<BigInteger> sequence = new List<BigInteger>();
List<BigInteger> primes = new List<BigInteger>();
sequence.Add(init);
bool halt = false;
while (primes.Count() < 20)
{
var k = FRACGAME.Compute(sequence[sequence.Count - 1]);
if (k.success)
sequence.Add(k.value);
else
{
halt = true;
break;
}
if (PowerOfTwo(k.value))
primes.Add(BigLog2(k.value));
}
for (int i = 0; i < primes.Count; i++)
Console.WriteLine((i + 1).ToString() + ": " + primes[i]);
if (halt)
Console.WriteLine("HALT");
}
}
</syntaxhighlight>
with the same input, will print the first 20 primes.
<pre>
1: 2
2: 3
3: 5
4: 7
5: 11
6: 13
7: 17
8: 19
9: 23
10: 29
11: 31
12: 37
13: 41
14: 43
15: 47
16: 53
17: 59
18: 61
19: 67
20: 71
</pre>
=={{header|C++}}==
<
#include <iostream>
#include <sstream>
Line 612 ⟶ 968:
return 0;
}
</syntaxhighlight>
{{out}}
<pre>
Line 631 ⟶ 987:
14 : 132
</pre>
=={{header|CLU}}==
<syntaxhighlight lang="clu">ratio = cluster is new, parse, unparse, get_num, get_denom, mul
rep = struct[num, denom: int]
new = proc (num, denom: int) returns (cvt)
return(simplify(rep${num: num, denom: denom}))
end new
parse = proc (rat: string) returns (ratio) signals (bad_format)
rat := trim(rat)
sep: int := string$indexc('/', rat)
if sep = 0 then signal bad_format end
num: string := string$substr(rat, 1, sep-1)
denom: string := string$rest(rat, sep+1)
return(new(int$parse(num), int$parse(denom))) resignal bad_format
end parse
trim = proc (s: string) returns (string)
start: int := 1
while start <= string$size(s) cand s[start] = ' ' do start := start + 1 end
end_: int := string$size(s)
while end_ >= 1 cand s[end_] = ' ' do end_ := end_ - 1 end
return(string$substr(s, start, end_-start+1))
end trim
unparse = proc (rat: cvt) returns (string)
return(int$unparse(rat.num) || "/" || int$unparse(rat.denom))
end unparse
get_num = proc (rat: cvt) returns (int)
return(rat.num)
end get_num
get_denom = proc (rat: cvt) returns (int)
return(rat.denom)
end get_denom
mul = proc (a, b: cvt) returns (ratio)
return(new(a.num * b.num, a.denom * b.denom))
end mul
simplify = proc (rat: rep) returns (rep)
num: int := int$abs(rat.num)
denom: int := int$abs(rat.denom)
sign: int
if (rat.num < 0) = (rat.denom < 0)
then sign := 1
else sign := -1
end
factor: int := gcd(num, denom)
return(rep${num: sign*num/factor, denom: denom/factor})
end simplify
gcd = proc (a, b: int) returns (int)
while b ~= 0 do
a, b := b, a // b
end
return(a)
end gcd
end ratio
fractran = cluster is parse, run
rep = sequence[ratio]
parse = proc (program: string) returns (cvt)
parsed: array[ratio] := array[ratio]$[]
for rat: ratio in ratioes(program) do
array[ratio]$addh(parsed, rat)
end
return(rep$a2s(parsed))
end parse
ratioes = iter (program: string) yields (ratio)
while true do
sep: int := string$indexc(',', program)
if sep = 0 then
yield(ratio$parse(program))
break
else
yield(ratio$parse(string$substr(program, 1, sep-1)))
program := string$rest(program, sep+1)
end
end
end ratioes
run = iter (program: cvt, n, maxiter: int) yields (int)
nrat: ratio := ratio$new(n, 1)
while maxiter > 0 do
yield(nrat.num)
begin
for rat: ratio in rep$elements(program) do
mul: ratio := rat * nrat
if mul.denom = 1 then
exit found(mul)
end
end
break
end except when found(new: ratio):
nrat := new
end
maxiter := maxiter - 1
end
end run
end fractran
start_up = proc ()
po: stream := stream$primary_output()
program: string := "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"
parsed: fractran := fractran$parse(program)
index: int := 0
for result: int in fractran$run(parsed, 2, 20) do
stream$putright(po, int$unparse(index), 3)
stream$putc(po, ':')
stream$putright(po, int$unparse(result), 10)
stream$putl(po, "")
index := index + 1
end
end start_up</syntaxhighlight>
{{out}}
<pre> 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
16: 308
17: 364
18: 68
19: 4</pre>
=={{header|Common Lisp}}==
<
(lambda ()
(prog1
Line 654 ⟶ 1,157:
for next = (funcall fractran-instance)
until (null next)
do (print next))</
{{out}}
Line 681 ⟶ 1,184:
===Simple Version===
{{trans|Java}}
<
void fractran(in string prog, int val, in uint limit) {
Line 698 ⟶ 1,201:
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);
}</
{{out}}
<pre>0: 2
Line 717 ⟶ 1,220:
===Lazy Version===
<
struct Fractran {
Line 742 ⟶ 1,245:
77/19 1/17 11/13 13/11 15/14 15/2 55/1", 2)
.take(15).writeln;
}</
{{out}}
<pre>[2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132]</pre>
=={{header|Delphi}}==
{{libheader| System.SysUtils}}
{{libheader| System.RegularExpressions}}
{{Trans|Java}}
<syntaxhighlight lang="delphi">
program FractranTest;
{$APPTYPE CONSOLE}
uses
System.SysUtils,
System.RegularExpressions;
type
TFractan = class
private
limit: Integer;
num, den: TArray<Integer>;
procedure compile(prog: string);
procedure exec(val: Integer);
function step(val: Integer): integer;
procedure dump();
public
constructor Create(prog: string; val: Integer);
end;
{ TFractan }
constructor TFractan.Create(prog: string; val: Integer);
begin
limit := 15;
compile(prog);
dump();
exec(2);
end;
procedure TFractan.compile(prog: string);
var
reg: TRegEx;
m: TMatch;
begin
reg := TRegEx.Create('\s*(\d*)\s*\/\s*(\d*)\s*');
m := reg.Match(prog);
while m.Success do
begin
SetLength(num, Length(num) + 1);
num[high(num)] := StrToIntDef(m.Groups[1].Value, 0);
SetLength(den, Length(den) + 1);
den[high(den)] := StrToIntDef(m.Groups[2].Value, 0);
m := m.NextMatch;
end;
end;
procedure TFractan.exec(val: Integer);
var
n: Integer;
begin
n := 0;
while (n < limit) and (val <> -1) do
begin
Writeln(n, ': ', val);
val := step(val);
inc(n);
end;
end;
function TFractan.step(val: Integer): integer;
var
i: integer;
begin
i := 0;
while (i < length(den)) and (val mod den[i] <> 0) do
inc(i);
if i < length(den) then
exit(round(num[i] * val / den[i]));
result := -1;
end;
procedure TFractan.dump();
var
i: Integer;
begin
for i := 0 to high(den) do
Write(num[i], '/', den[i], ' ');
Writeln;
end;
const
DATA =
'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';
begin
TFractan.Create(DATA, 2).Free;
Readln;
end.</syntaxhighlight>
{{out}}
<pre>
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: 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
</pre>
=={{header|Elixir}}==
{{trans|Erlang}}
<
use Bitwise
Line 813 ⟶ 1,431:
|> Enum.map(&Fractran.lowbit/1)
|> tl
IO.puts "The first few primes are:\n#{inspect prime}"</
{{out}}
Line 826 ⟶ 1,444:
=={{header|Erlang}}==
The exec() function can be passed a predicate which filters steps that satisfy a condition, which for the prime automata is a check to see if the number is a power of 2.
<
-mode(native).
Line 885 ⟶ 1,503:
gcd(A, 0) -> A;
gcd(A, B) -> gcd(B, A rem B).
</syntaxhighlight>
{{out}}
<pre>
Line 901 ⟶ 1,519:
=={{header|Factor}}==
<
prettyprint sequences splitting ;
IN: rosetta-code.fractran
Line 935 ⟶ 1,553:
2bi ;
MAIN: main</
{{out}}
<pre>
Line 943 ⟶ 1,561:
First 20 primes:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71
</pre>
=={{header|Fermat}}==
<syntaxhighlight lang="fermat">Func FT( arr, n, m ) =
;{executes John H. Conway's FRACTRAN language for a program stored in [arr], an}
;{input integer stored in n, for a maximum of m steps}
;{To allow the program to run indefinitely, give it negative or noninteger m}
exec:=1; {boolean to track whether the program needs to halt}
len:=Cols[arr]; {length of the input program}
while exec=1 and m<>0 do
m:-;
!!n; {output the memory}
i:=1; {index variable}
exec:=0;
while i<=len and exec=0 do
nf:=n*arr[i];
if Denom(nf) = 1 then
n:=nf; {did we find an instruction to execute?}
exec:=1
fi;
i:+;
od;
od;
.;
;{Here is the program to run}
[arr]:=[( 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 )];
FT( [arr], 2, 20 );</syntaxhighlight>
{{out}}<pre>
2
15
825
725
1925
2275
425
390
330
290
770
910
170
156
132
116
308
364
68
4
</pre>
Line 950 ⟶ 1,618:
===The Code===
The source style is F77 except for the use of the I0 format code, though not all F77 compilers will offer INTEGER*8. By not using the MODULE scheme, array parameters can't be declared via P(:) which implies a secret additional parameter giving the size of the array and which can be accessed via the likes of <code>UBOUND(P, DIM = 1)</code> Instead, the old-style specification involves no additional parameters and can be given as P(*) meaning "no statement" as to the upper bound, or P(M) which ''may'' be interpreted as the upper bound being the value of M in the compilers that allow this. The actual upper bound of the parameter is unknown and unchecked, so the older style of P(12345) or similar might be used. Rather to my surprise, this compiler (Compaq F90/95) complained if parameter M was declared after the arrays P(M),Q(M) as it is my habit to declare parameters in the order of their appearance. <
INTEGER P(M),Q(M)!The terms of the fractions.</
So much for multi-pass compilers!
Similarly, without the MODULE protocol, in all calling routines function FRACTRAN would be deemed floating-point so a type declaration is needed in each. <
Careful: the rule is N*P/Q being integer. N*6/3 is integer always because this is N*2/1, but 3 may not divide N.
Could check GCD(P,Q), dividing out the common denominator so MOD(N,Q) works.
Line 1,003 ⟶ 1,671:
END DO !The next step.
END !Whee!
</syntaxhighlight>
===The Results===
Line 1,044 ⟶ 1,712:
28 1: 14875
</pre>
Later Fortrans might offer the library function <code>POPCNT(n)</code> which returns the number of on-bits in an integer, most convenient for detecting a straight power of two in a binary computer. Adjusting the interpretation loop to be <
IT = FRACTRAN(N,P,Q,L) !Do it!
IF (POPCNT(N).EQ.1) WRITE (6,11) I,IT,N !Show it!
Line 1,055 ⟶ 1,723:
END IF !So much for overflow.
END DO !The next step.
</syntaxhighlight>
Leads to the following output:
<pre>
Line 1,090 ⟶ 1,758:
===Revised Code===
Because this scheme requires a supply of prime numbers, it is convenient to employ the routines prepared for the [[Extensible_prime_generator|extensible prime generator]] via module PRIMEBAG. So, this means escalating to the F90 style, and given that, some compound data structures can be used (for better mnemonics) in place of collections of arrays. <
USE PRIMEBAG !This is a common need.
INTEGER LASTP,ENUFF !Some size allowances.
Line 1,277 ⟶ 1,945:
Complete!
END !Whee!
</syntaxhighlight>
===Revised Results===
Line 1,392 ⟶ 2,060:
100 7: 3 1 1 1
</pre>
This time, restricting output to only occasions when N is a power of two requires no peculiar bit-counting function. Just change the interpretation loop to <
IT = FRACTRAN(LF) !Do it!
IF (ALL(NPPOW(2:LP).EQ.0)) CALL SHOWN(I,IT) !Show it!
IF (IT.LE.0) EXIT !Quit it?
END DO !The next step.</
Output:
Line 1,510 ⟶ 2,178:
=={{header|FreeBASIC}}==
Added a compiler condition to make the program work with the old GMP.bi header file
<
' compile with: fbc -s console
' uses gmp
Line 1,599 ⟶ 2,267:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre>2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116
Line 1,627 ⟶ 2,295:
42 34533967 181
43 40326168 191</pre>
=={{header|Fōrmulæ}}==
{{FormulaeEntry|page=https://formulae.org/?script=examples/FRACTRAN}}
'''Solution'''
[[File:Fōrmulæ - FRACTRAN 01.png]]
It is a function that accepts the program to run (as a list), the initial value of n and the number of values to generate.
It uses a local nested function next() that calculates the next value of . If it can be calculated, it is added to a result array and return true, elsewhere return false.
The main work is to iterate while the next() returns true and the number of values to generate is not reached.
The following is the call with the program for primes, initial n value of 2, and returning 20 values:
[[File:Fōrmulæ - FRACTRAN 02.png]]
[[File:Fōrmulæ - FRACTRAN 03.png]]
'''Bonus''' using the previous FRACTAN program to generate the first 20 primes.
It requires a modification to the previous program.
[[File:Fōrmulæ - FRACTRAN 04.png]]
[[File:Fōrmulæ - FRACTRAN 05.png]]
[[File:Fōrmulæ - FRACTRAN 06.png]]
'''FRACTRAN program for addition'''
[[File:Fōrmulæ - FRACTRAN 07.png]]
[[File:Fōrmulæ - FRACTRAN 08.png]]
[[File:Fōrmulæ - FRACTRAN 09.png]]
'''FRACTRAN program for multiplication'''
[[File:Fōrmulæ - FRACTRAN 10.png]]
[[File:Fōrmulæ - FRACTRAN 11.png]]
[[File:Fōrmulæ - FRACTRAN 12.png]]
=={{header|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.
<
import (
Line 1,691 ⟶ 2,405:
}
exec(p, &n, limit)
}</
{{out|Command line usage, with program compiled as "ft"}}
<pre>
Line 1,699 ⟶ 2,413:
Extra credit: This invokes above program with appropriate arguments,
and processes the output to obtain the 20 primes.
<
import (
Line 1,733 ⟶ 2,447:
}
fmt.Println()
}</
{{out}}
<pre>
Line 1,741 ⟶ 2,455:
=={{header|Haskell}}==
===Running the program===
<
import Data.Ratio (Ratio, (%), denominator)
Line 1,748 ⟶ 2,462:
case find (\f -> n `mod` denominator f == 0) fracts of
Nothing -> []
Just f -> fractran fracts $ truncate (fromIntegral n * f)</
Example:
Line 1,758 ⟶ 2,472:
===Reading the program===
Additional import
<syntaxhighlight lang
<
readProgram = map (toFrac . splitOn "/") . splitOn ","
where toFrac [n,d] = read n % read d</
Example of running the program:
Line 1,771 ⟶ 2,485:
===Generation of primes===
Additional import
<
import Data.List (elemIndex)</
<
primes = mapMaybe log2 $ fractran prog 2
where
Line 1,792 ⟶ 2,506:
, 55 % 1
]
log2 = fmap succ . elemIndex 2 . takeWhile even . iterate (`div` 2)</
<pre>λ> take 20 primes
Line 1,800 ⟶ 2,514:
Works in both languages:
<
procedure main(A)
Line 1,826 ⟶ 2,540:
}
write()
end</
{{out}}
Line 1,836 ⟶ 2,550:
=={{header|J}}==
===Hybrid version===
'''Solution:'''
<
fractran15=: ({~ (= <.) i. 1:)@(toFrac@[ * ]) ^:(<15) NB. return first 15 Fractran results</
'''Example:'''
<
taskstr fractran15 2
2 15 825 725 1925 2275 425 390 330 290 770 910 170 156 132</
===Tacit version===
'''Solution'''
This is a variation of the previous solution which it is not entirely tacit due to the use of the explicit standard library verb (function) charsub. The adverb (functional) fractran is defined as a fixed tacit adverb (that is, a stateless point-free functional),
<syntaxhighlight lang="j">fractran=. (((({~ (1 i.~ (= <.)))@:* ::]^:)(`]))(".@:('1234567890r ' {~ '1234567890/ '&i.)@:[`))(`:6)</syntaxhighlight>
The argument of fractran specifies a limit for the number of steps; if the limit is boxed the intermediate results are also included in the result.
'''Example'''
<syntaxhighlight lang="j"> '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' (<15) fractran 2
2 15 825 725 1925 2275 425 390 330 290 770 910 170 156 132</syntaxhighlight>
'''Extra credit'''
The prime numbers are produced via the adverb primes; its argument has the same specifications as the argument for the fractran adverb (which is used in its definition),
<syntaxhighlight lang="j">primes=. ('fractan'f.) ((1 }. 2 ^. (#~ *./@:e.&2 0"1@:q:))@:)
'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' (<555555) primes 2
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71</syntaxhighlight>
primes is also a stateless point-free functional,
<syntaxhighlight lang="j"> primes
((((({~ (1 i.~ (= <.)))@:* ::]^:)(`]))(".@:('1234567890r ' {~ '1234567890/ '&i.)@:[`))(`:6))((1 }. 2 ^. (#~ *./@:e.&2 0"1@:q:))@:)</syntaxhighlight>
'''Turing completeness of J's stateless point-free dialect'''
When _ is the limit argument (i.e., when no limit is imposed) the run will halt according to the FRACTRAN programming language specifications (the run might also be forced to halt if a trivial changeless single cycle, induced by a useless 1/1 fraction, is detected). Thus, the FRACTRAN associated verb (function) is,
<syntaxhighlight lang="j"> _ fractran
".@:('1234567890r ' {~ '1234567890/ '&i.)@:[ ({~ (1 i.~ (= <.)))@:* ::]^:_ ]</syntaxhighlight>
Actually, most of the code above is there to comply with the task's requirement of a "''natural'' format." When J's format for fractions is used the FRACTRAN verb becomes,
<syntaxhighlight lang="j">FRACTRAN=. ({~ (1 i.~ (= <.)))@:* ::]^:_</syntaxhighlight>
which is an indirect concise confirmation that J's fixed tacit dialect is Turing complete.
In the following example, FRACTRAN calculates the product 4 * 6, the initial value 11664 = (2^4)*(3^6) holds 4 in the register associated with 2 and holds 6 in the register associated with 3; the result 59604644775390625 = 5^24 holds the product 24 = 4 * 6 in the register associated with 5,
<syntaxhighlight lang="j"> 455r33 11r13 1r11 3r7 11r2 1r3 FRACTRAN 11664
59604644775390625</syntaxhighlight>
=={{header|Java}}==
<
import java.util.regex.Matcher;
import java.util.regex.Pattern;
Line 1,899 ⟶ 2,664:
System.out.println();
}
}</
=={{header|JavaScript}}==
===Imperative===
<
function compile(prog, numArr, denArr) {
let regex = /\s*(\d*)\s*\/\s*(\d*)\s*(.*)/m;
Line 1,947 ⟶ 2,712:
let [num, den] = 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", [], []);
body.innerHTML = dump(num, den);
body.innerHTML += exec(2, 0, 15, num, den);</
===Functional===
Line 1,953 ⟶ 2,718:
Here is a functionally composed version, which also derives a few primes. I may have missed something, but this first draft suggests that we may need bigInt support (which JS lacks) to get as far as the sixth prime.
<
'use strict';
Line 1,959 ⟶ 2,724:
const fractran = (xs, n) => {
function* go(n) {
const p = r => 0 === v % r.d;
let
v = n,
mb = find(
yield v
while (!mb.Nothing) {
mb = bindMay(
find(
r => (
v = truncate({
Line 2,043 ⟶ 2,809:
length: 2
});
// abs :: Num -> Num
Line 2,052 ⟶ 2,816:
const bindMay = (mb, mf) =>
mb.Nothing ? mb : mf(mb.Just);
// div :: Int -> Int -> Int
Line 2,081 ⟶ 2,838:
return Nothing();
};
// fmapMay (<$>) :: (a -> b) -> Maybe a -> Maybe b
Line 2,108 ⟶ 2,855:
return _gcd(abs(x), abs(y));
};
// iterate :: (a -> a) -> a -> Gen [a]
Line 2,134 ⟶ 2,877:
}
}
// properFracRatio :: Ratio -> (Int, Ratio)
Line 2,234 ⟶ 2,959:
// MAIN ---
return main();
})();</
{{Out}}
<pre>"First fifteen steps:" -> [2,15,825,725,1925,2275,425,390,330,290,770,910,170,156,132]
Line 2,240 ⟶ 2,965:
=={{header|Julia}}==
{{works with|Julia|
# FRACTRAN interpreter implemented as an iterable struct
using .Iterators: filter, map, take
struct Fractran
rs::Vector{Rational{BigInt}}
end
Base.iterate(f::Fractran, i = f.i₀) =
for r in f.rs
if iszero(i % r.den)
i = i ÷ r.den * r.num
return i, i
end
end
interpret(f::Fractran) =
take(
map(trailing_zeros,
filter(ispow2, f))
f.limit)
Base.show(io::IO, f::Fractran) =
join(io, interpret(f), ' ')
macro code_str(s)
[eval(Meta.parse(replace(t, "/" => "//"))) for t ∈ split(s)]
end
# Output
println("First 25 iterations of FRACTRAN program 'primes':\n2 ",
join(take(primes, 25), ' '))
println("\nWatch the first 30 primes dropping out within seconds:")
primes</syntaxhighlight>
{{output}}
<pre>First 25 iterations of FRACTRAN program 'primes':
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
Watch the first 30 primes dropping out within seconds:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113
</pre>
=={{header|Kotlin}}==
<
import java.math.BigInteger
Line 2,342 ⟶ 3,060:
println("\nFirst twenty primes:")
println(fractran(program, 2, 20, true))
}</
{{out}}
Line 2,356 ⟶ 3,074:
This isn't as efficient as possible for long lists of fractions, since it doesn't stop doing n*listelements once it finds an integer. Instead, it computes "is integer?" for n*{all list elements}. For short lists that's probably not a big deal.
<
n = 2;
steplimit = 20;
Line 2,370 ⟶ 3,088:
n = newlist[[truepositions[[1, 1]]]]; j++;
]
]</
{{out}}
<pre>0: 2
Line 2,393 ⟶ 3,111:
19: 4
20: 30</pre>
===Functional Version===
Here is a different solution using a functional approach:
<syntaxhighlight lang="mathematica">
fractran[
program : {__ ? (Element[#, PositiveRationals] &)}, (* list of positive fractions *)
n0_Integer, (* initial state *)
maxSteps : _Integer : Infinity] := (* max number of steps *)
NestWhileList[ (* Return a list representing the evolution of the state n *)
Function[n, SelectFirst[IntegerQ][program * n]], (* Select first integer in n*program, if none return Missing *)
n0,
Not @* MissingQ, (* continue while the state is not Missing *)
1,
maxSteps]
$PRIMEGAME = {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};
fractran[$PRIMEGAME, 2, 50]
</syntaxhighlight>
{{out}}
<pre>{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}</pre>
Extract the first 20 prime numbers encoded as powers of 2:
<syntaxhighlight lang="mathematica">
Select[IntegerQ] @ Log2[fractran[$PRIMEGAME, 2, 500000]]
</syntaxhighlight>
{{out}}
<pre>{1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67}</pre>
=={{header|Nim}}==
=== Using fractions===
{{libheader|bignum}}
This is a simple implementation which operates on fractions. As Nim standard library doesn’t provide a module for big numbers, we have used the extra library “bignum” which relies on “gmp”.
We provide a general function to run any Fractran program and a specialized iterator to find prime numbers.
<syntaxhighlight lang="nim">
import strutils
import bignum
const PrimeProg = "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"
iterator values(prog: openArray[Rat]; init: Natural): Int =
## Run the program "prog" with initial value "init" and yield the values.
var n = newInt(init)
var next: Rat
while true:
for fraction in prog:
next = n * fraction
if next.denom == 1:
break
n = next.num
yield n
func toFractions(fractList: string): seq[Rat] =
## Convert a string to a list of fractions.
for f in fractList.split():
result.add(newRat(f))
proc run(progStr: string; init: Natural; maxSteps: Natural = 0) =
## Run the program described by string "progStr" with initial value "init",
## stopping after "maxSteps" (0 means for ever).
## Display the value after each step.
let prog = progStr.toFractions()
var stepCount = 0
for val in prog.values(init):
inc stepCount
echo stepCount, ": ", val
if stepCount == maxSteps:
break
iterator primes(n: Natural): int =
# Yield the list of first "n" primes.
let prog = PrimeProg.toFractions()
var count = 0
for val in prog.values(2):
if isZero(val and (val - 1)):
# This is a power of two.
yield val.digits(2).int - 1 # Compute the exponent as number of binary digits minus one.
inc count
if count == n:
break
# Run the program to compute primes displaying values at each step and stopping after 10 steps.
echo "First ten steps for program to find primes:"
PrimeProg.run(2, 10)
# Find the first 20 primes.
echo "\nFirst twenty prime numbers:"
for val in primes(20):
echo val
</syntaxhighlight>
{{out}}
<pre>
First ten steps for program to find primes:
1: 15
2: 825
3: 725
4: 1925
5: 2275
6: 425
7: 390
8: 330
9: 290
10: 770
First twenty prime numbers:
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47
53
59
61
67
71
</pre>
===Using decomposition in prime factors===
With this algorithm, we no longer need big numbers. To avoid overflow, value at each step is displayed using
its decomposition in prime factors.
<syntaxhighlight lang="nim">
import algorithm
import sequtils
import strutils
import tables
const PrimeProg = "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"
type
Fraction = tuple[num, denom: int]
Factors = Table[int, int]
FractranProg = object
primes: seq[int]
nums, denoms: seq[Factors]
exponents: seq[int] # Could also use a CountTable.
iterator fractions(fractString: string): Fraction =
## Extract fractions from a string and yield them.
for f in fractString.split():
let fields = f.strip().split('/')
assert fields.len == 2
yield (fields[0].parseInt(), fields[1].parseInt())
iterator factors(val: int): tuple[val, exp: int] =
## Extract factors from a positive integer.
# Extract factor 2.
var val = val
var exp = 0
while (val and 1) == 0:
inc exp
val = val shr 1
if exp != 0:
yield (2, exp)
# Extract odd factors.
var d = 3
while d <= val:
exp = 0
while val mod d == 0:
inc exp
val = val div d
if exp != 0:
yield (d, exp)
inc d, 2
func newProg(fractString: string; init: int): FractranProg =
## Initialize a Fractran program.
for f in fractString.fractions():
# Extract numerators factors.
var facts: Factors
for (val, exp) in f.num.factors():
result.primes.add(val)
facts[val] = exp
result.nums.add(facts)
# Extract denominator factors.
facts.clear()
for (val, exp) in f.denom.factors():
result.primes.add(val)
facts[val] = exp
result.denoms.add(facts)
# Finalize list of primes.
result.primes.sort()
result.primes = result.primes.deduplicate(true)
# Allocate and initialize exponent sequence.
result.exponents.setLen(result.primes[^1] + 1)
for (val, exp) in init.factors():
result.exponents[val] = exp
func doOneStep(prog: var FractranProg): bool =
## Execute one step of the program.
for idx, factor in prog.denoms:
block tryFraction:
for val, exp in factor.pairs():
if prog.exponents[val] < exp:
# Not a multiple of the denominator.
break tryFraction
# Divide by the denominator.
for val, exp in factor.pairs():
dec prog.exponents[val], exp
# Multiply by the numerator.
for val, exp in prog.nums[idx]:
inc prog.exponents[val], exp
return true
func `$`(prog: FractranProg): string =
## Display a value as a product of prime factors.
for val, exp in prog.exponents:
if exp != 0:
if result.len > 0:
result.add('.')
result.add($val)
if exp > 1:
result.add('^')
result.add($exp)
proc run(fractString: string; init: int; maxSteps = 0) =
## Run a Fractran program.
var prog = newProg(fractString, init)
var stepCount = 0
while stepCount < maxSteps:
if not prog.doOneStep():
echo "*** No more possible fraction. Program stopped."
return
inc stepCount
echo stepCount, ": ", prog
proc findPrimes(maxCount: int) =
## Search and print primes.
var prog = newProg(PrimeProg, 2)
let oddPrimes = prog.primes[1..^1]
var primeCount = 0
while primeCount < maxCount:
discard prog.doOneStep()
block powerOf2:
if prog.exponents[2] > 0:
for p in oddPrimes:
if prog.exponents[p] != 0:
# Not a power of 2.
break powerOf2
inc primeCount
echo primeCount, ": ", prog.exponents[2]
#------------------------------------------------------------------------------
echo "First ten steps for program to find primes:"
run(PrimeProg, 2, 10)
echo "\nFirst twenty prime numbers:"
findPrimes(20)
</syntaxhighlight>
{{out}}
<pre>
First ten steps for program to find primes:
1: 3.5
2: 3.5^2.11
3: 5^2.29
4: 5^2.7.11
5: 5^2.7.13
6: 5^2.17
7: 2.3.5.13
8: 2.3.5.11
9: 2.5.29
10: 2.5.7.11
First twenty prime numbers:
1: 2
2: 3
3: 5
4: 7
5: 11
6: 13
7: 17
8: 19
9: 23
10: 29
11: 31
12: 37
13: 41
14: 43
15: 47
16: 53
17: 59
18: 61
19: 67
20: 71
</pre>
=={{header|OCaml}}==
This reads a Fractran program from standard input (keyboard or file) and runs it with the input given by the command line arguments, using arbitrary-precision numbers and fractions.
<
let get_input () =
Line 2,438 ⟶ 3,466:
let num = get_input () in
let prog = read_program () in
run_program num prog</
The program
Line 2,488 ⟶ 3,516:
{{Works with|PARI/GP|2.7.4 and above}}
<
\\ FRACTRAN
\\ 4/27/16 aev
Line 2,504 ⟶ 3,532:
print(fractran(2,v,15));
}
</
{{Output}}
Line 2,516 ⟶ 3,544:
This makes the fact that it's a prime-number-generating program much clearer.
<
use warnings;
use Math::BigRat;
Line 2,547 ⟶ 3,575:
print "\n";
</syntaxhighlight>
If you uncomment the <pre>#print $n</pre>, it will print all the steps.
=={{header|
Using the same ideas as the Fortran entry (thanks!).
For example, suppose that known_factors happens to be {2,3,5}. [the exact order may vary]<br>
2 is held as {1,0,0}, ie 2^1 * 3^0 * 5^0, and 15 as {0,1,1}, ie 2^0 * 3^1 * 5^1.
Notice that 2, being a power of 2, has zero in all slots other than 2.<br>
We can say that (eg) 15 is not exactly divisible by 2 because an sq_sub({0,1,1},{1,0,0}) would contain some <0s.<br>
We can also say that 15 is not a power of 2 because there are non-0 in other than n[find(2,known_factors)].<br>
Division (to whole integer) is performed simply by subtracting the corresponding powers, as above not possible if any would be negative.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">without</span> <span style="color: #008080;">js</span> <span style="color: #000080;font-style:italic;">-- 8s
--with javascript_semantics -- 52s!! (see note)</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">steps</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">20</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">primes</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">45</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">known_factors</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span> <span style="color: #000080;font-style:italic;">-- nb: no specific order</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">combine_factors</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- (inverse of as_primes)</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">*=</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">known_factors</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">n</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">as_primes</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- eg as_primes(55) -> {5,11} -> indexes to known_factors</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #0000FF;">{}</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">pf</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">prime_factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">duplicates</span><span style="color: #0000FF;">:=</span><span style="color: #004600;">true</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">known_factors</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pf</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pf</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">known_factors</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">known_factors</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">known_factors</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pf</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000080;font-style:italic;">-- atom chk = combine_factors(res)
-- if chk!=n then ?9/0 end if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">parse</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">split</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">sri</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">scanf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #008000;">"%d/%d"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">sri</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> <span style="color: #000080;font-style:italic;">-- oops!</span>
<span style="color: #004080;">integer</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">}}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">sri</span>
<span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">as_primes</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">),</span><span style="color: #000000;">as_primes</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)}</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">step</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">pgm</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">pc</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pgm</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pgm</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pc</span><span style="color: #0000FF;">][</span><span style="color: #000000;">2</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span>
<span style="color: #000080;font-style:italic;">-- sequence d = pgm[pc][2], res = deep_copy(n) -- (see timing note)</span>
<span style="color: #004080;">bool</span> <span style="color: #000000;">ok</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">df</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">[</span><span style="color: #000000;">f</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">df</span><span style="color: #0000FF;">!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">f</span><span style="color: #0000FF;">></span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">or</span> <span style="color: #000000;">df</span><span style="color: #0000FF;">></span><span style="color: #000000;">n</span><span style="color: #0000FF;">[</span><span style="color: #000000;">f</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">ok</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">false</span>
<span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">f</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">df</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">ok</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">pgm</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pc</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">zf</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)-</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">zf</span><span style="color: #0000FF;">></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #000000;">zf</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">src</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"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"</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">pgm</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">parse</span><span style="color: #0000FF;">(</span><span style="color: #000000;">src</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">object</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">as_primes</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">steps</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">step</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pgm</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">combine_factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"first %d results: %v\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">steps</span><span style="color: #0000FF;">,</span><span style="color: #000000;">res</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">as_primes</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">k2</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">known_factors</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">n0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">0</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">known_factors</span><span style="color: #0000FF;">))</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">iteration</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #008080;">while</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)<</span><span style="color: #000000;">primes</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">step</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pgm</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">n0</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k2</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">n0</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">-- (ie all non-2 are 0)
-- and the prime itself is ready and waiting...</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">[</span><span style="color: #000000;">k2</span><span style="color: #0000FF;">])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">iteration</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"first %d primes: %v\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">primes</span><span style="color: #0000FF;">,</span><span style="color: #000000;">res</span><span style="color: #0000FF;">})</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%,d iterations in %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">iteration</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)})</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
first 20 results: {15,825,725,1925,2275,425,390,330,290,770,910,170,156,132,116,308,364,68,4,30}
first 45 primes: {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,
107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197}
10,494,775 iterations in 8.4s
</pre>
For comparison with that 8.4s, I've collected Python: 386s, REXX: 60s for 25 (on tio, then it timed out), Ruby: 187s, Go: 1736s(!!), Julia 616s, FreeBasic 11.7s<br>
(Clearly the algorithms being used are way more significant than any inherent programming language differences here.)<br>
Update 17/01/2022: Also note that 8.4s is for desktop/Phix, without js. Adding with js and the required deep_copy() makes it about 6.5 times slower, though it actually fares somewhat better(/less awful) in a browser (30s vs 50s). Clearly the current hll implementation of deep_copy(), as first shipped in July 2021, is nowhere near as efficient as the older low-level "clone that must be avoided", at least not yet.
=={{header|
<syntaxhighlight lang="prolog">
load(Program, Fractions) :-
re_split("[ ]+", Program, Split), odd_items(Split, TextualFractions),
maplist(convert_frac, TextualFractions, Fractions).
odd_items(L, L) :- L = [_], !. % remove the even elements from a list.
odd_items([X,_|L], [X|R]) :- odd_items(L, R).
convert_frac(Text, Frac) :-
re_matchsub("([0-9]+)/([0-9]+)"/t, Text, Match, []),
Frac is Match.1 rdiv Match.2.
step(_, [], stop) :- !.
step(N, [F|Fs], R) :-
(integer(A) -> R = A; step(N, Fs, R)).
exec(Prg, Start, Lz) :-
lazy_list(transition, Prg/Start, Lz).
transition(Prg/N0, Prg/N1, N1) :-
step(N0, Prg, N1).
steps(K, Start, Prg, Seq) :-
exec(Prg, Start, Values),
length(Seq, K), Seq = [Start|Rest], prefix(Rest, Values), !.
% The actual PRIMEGEN program follows...
primegen(Prg) :-
load("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", Prg).
primes(N, Primes) :-
primegen(Prg), exec(Prg, 2, Steps),
length(Primes, N), capture_primes(Primes, Steps).
capture_primes([], _) :- !.
capture_primes([P|Ps], [Q|Qs]) :- pow2(Q), !, P is lsb(Q), capture_primes(Ps, Qs).
capture_primes(Ps, [_|Qs]) :- capture_primes(Ps, Qs).
pow2(X) :- X /\ (X-1) =:= 0.
main :-
primegen(Prg), steps(15, 2, Prg, Steps),
format("The first 15 steps from PRIMEGEN are: ~w~n", [Steps]),
primes(20, Primes),
format("By running PRIMEGEN we found these primes: ~w~n", [Primes]),
halt.
?- main.
</syntaxhighlight>
{{Out}}
<pre>
The first
</pre>
=={{header|Python}}==
===Python: Generate series from a fractran program===
<
def fractran(n, fstring='17 / 91, 78 / 85, 19 / 51, 23 / 38, 29 / 33,'
Line 2,709 ⟶ 3,789:
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))))</
{{out}}
Line 2,718 ⟶ 3,798:
Use fractran above as a module imported into the following program.
<
from fractran import fractran
Line 2,731 ⟶ 3,811:
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))</
{{out}}
Line 2,749 ⟶ 3,829:
Generated prime 43 from the 117832'th member of the fractran series
Generated prime 47 from the 152026'th member of the fractran series</pre>
=={{header|Quackery}}==
<code>run</code> performs the first step of executing a Fractran program, returning a rational number (represented as two stack items: numerator and denominator) and a boolean. The boolean is <code>true</code> if the halting condition is satisfied, and <code>false</code> otherwise.
In this task the parsed Fractran program is stored on the ancillary stack <code>program</code>.
To execute a Fractran program until the halting condition is satisfied, use <code>[ program share run until ]</code>. The Fractran prime generator will never satisfy the halting condition, so in this task the <code>drop</code> after <code>run</code> discards the boolean.
<syntaxhighlight lang="quackery"> [ $ "bigrat.qky" loadfile ] now!
[ 1 & not ] is even ( n --> b )
[ nip 1 = ] is vint ( n/d --> b )
[ [ dup even while
1 >> again ]
1 = ] is powerof2 ( n --> b )
[ 0 swap
[ dup even while
dip 1+
1 >> again ]
drop ] is lowbit ( n --> n )
[ [] swap nest$
witheach
[ char / over find
space unrot poke
build nested join ] ] is parse$ ( $ --> [ )
[ stack ] is program ( s --> )
[ true temp put
witheach
[ do 2over v*
2dup vint iff
[ false temp replace
conclude ]
else 2drop ]
2swap 2drop
temp take ] is run ( n/d [ --> n/d b )
[ stack ] is primes ( --> 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" join
parse$ program put
2 n->v
15 times
[ program share run
drop over echo sp ]
cr
2drop
2 n->v
[] primes put
[ program share run
drop over dup powerof2 iff
[ lowbit primes take
swap join primes put ]
else drop
primes share size 20 = until ]
2drop
primes take echo
program release
</syntaxhighlight>
{{out}}
<pre>
15 825 725 1925 2275 425 390 330 290 770 910 170 156 132 116
[ 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 ]
</pre>
=={{header|Racket}}==
{{trans|D}} Simple version, without sequences.
<
(define (displaysp x)
Line 2,782 ⟶ 3,937:
"13 / 11, 15 / 14, 15 / 2, 55 / 1")))
(show-fractran fractran 2 15)</
{{out}}
<pre>First 15 members of fractran(2):
2 15 825 725 1925 2275 425 390 330 290 770 910 170 156 132</pre>
=={{header|Raku}}==
(formerly Perl 6)
{{works with|rakudo|2015-11-03}}
A Fractran program potentially returns an infinite list, and infinite lists are a common data structure in Raku. The limit is therefore enforced only by slicing the infinite list.
<syntaxhighlight lang="raku" line>sub fractran(@program) {
2, { first Int, map (* * $_).narrow, @program } ... 0
}
say 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>)[^100];</syntaxhighlight>
{{out}}
<pre>(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)</pre>
'''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 <tt>.msb</tt> method finds the most significant bit of an integer, which conveniently is the base-2 log of the power-of-two in question.
<syntaxhighlight lang="raku" line>sub fractran(@program) {
2, { first Int, map (* * $_).narrow, @program } ... 0
}
for 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> {
say $++, "\t", .msb, "\t", $_ if 1 +< .msb == $_;
}</syntaxhighlight>
{{out}}
<pre>
0 1 2
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
^C</pre>
=={{header|Red}}==
<syntaxhighlight lang="red">Red ["Fractran"]
inp: ask "please enter list of fractions, or input file name: "
if exists? inpf: to-file inp [inp: read inpf]
digit: charset "0123456789"
frac: [copy p [some digit] #"/" copy q [some digit]
keep (as-pair to-integer p to-integer q)]
code: parse inp [collect [frac some [[some " "] frac]]]
n: to-integer ask "please enter starting number n: "
x: to-integer ask "please enter the number of terms, hit return for no limit: "
l: length? code
loop x [
forall code [
c: code/1
if n % c/y = 0 [
print n: n / c/y * c/x
code: head code
break
]
if l = index? code [halt]
]
]</syntaxhighlight>
{{out}}
<pre>please enter list of fractions, or input file name: 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
please enter starting number n: 2
please enter the number of terms, hit return for no limit: 15
15
825
725
1925
2275
425
390
330
290
770
910
170
156
132
116</pre>
=={{header|REXX}}==
Programming note: extra blanks can be inserted in the fractions before and/or after the solidus ['''<big>/</big>'''].
===showing all terms===
<
numeric digits 2000 /*be able to handle larger numbers. */
parse arg N terms fracs /*obtain optional arguments from the CL*/
if N==''
if terms=='' | terms=="," then terms=
if fracs='' then fracs=
'77/19, 1/17, 11/13, 13/11, 15/14, 15/2, 55/1'
/* [↑] The default for the fractions. */
f= space(fracs, 0)
do #=1 while f\==''; parse var f n.#
end /*#*/
#= # -
say # 'fractions:' fracs /*display number 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
cN=
say
N=
leave
end /*j*/
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ?</syntaxhighlight>
{{out|output|text= when using the default input:}}
<pre style="height:63ex">
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 ──►
term 6 ──►
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 ──►
term 24 ──►
term 25 ──►
term 26 ──►
term 27 ──►
term 28 ──►
term 29 ──►
term 30 ──►
term 31 ──►
term 32 ──►
term 33 ──►
term 34 ──►
term 35 ──►
term 36 ──►
term 37 ──►
term 38 ──►
term 39 ──►
term 40 ──►
term 41 ──► 408
term 42 ──► 152
term 43 ──► 92
term 44 ──► 380
term 45 ──► 230
term 46 ──► 950
term 47 ──► 575
term 48 ──►
term 49 ──►
term 50 ──►
term 51 ──►
term 52 ──►
term 53 ──►
term 54 ──►
term 55 ──►
term 56 ──►
term 57 ──► 850
term 58 ──► 780
term 59 ──► 660
term 60 ──► 580
term 61 ──►
term 62 ──►
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 ──►
term 74 ──►
term 75 ──►
term 76 ──►
term 77 ──►
term 78 ──►
term 79 ──►
term 80 ──►
term 81 ──►
term 82 ──►
term 83 ──►
term 84 ──►
term 85 ──►
term 86 ──►
term 87 ──►
term 88 ──►
term 89 ──►
term 90 ──►
term 91 ──►
term 92 ──►
term 93 ──►
term 94 ──►
term 95 ──►
term 96 ──►
term 97 ──►
term 98 ──►
term 99 ──►
term 100 ──►
</pre>
===showing prime numbers===
Programming note: if the number of terms specified (the 2<sup>nd</sup> argument) is negative, then only powers of two are displayed.
<
numeric digits 999;
parse arg N terms fracs /*obtain optional arguments from the CL*/
if N==''
if terms=='' | terms=="," then terms=
if fracs='' then fracs=
'77/19, 1/17, 11/13, 13/11, 15/14, 15/2, 55/1'
/* [↑] The default for the fractions. */
f= space(fracs, 0)
do #=1 while f\==''; parse var f n.#
end /*#*/
#= # -
tell= terms>0 /*flag: show number or a power of 2.*/
!.= 0;
if \tell then do p=1 until length(_)>
if p==1 then @._= left('', w + 9)
else @._= '(prime' right(p, w)") 2**"left(p, w) ' '
end /*p*/ /* [↑] build powers of 2 tables. */
L= length(N)
say # 'fractions:' fracs /*display number and actual fractions. */
say 'N is starting at ' N /*display the starting number N. */
if tell then say terms ' terms are being shown:'
else say 'only powers of two are being shown:'
cN= commas(N);
N= N
L= max(L, length(N)
leave
end
end /*j*/
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ?</syntaxhighlight>
{{out|output|text= when using the input (negative fifty million) of: <tt> , -50000000 </tt>}}
<pre>
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
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
term
term
term
term
term
term
term
term 101,113 ──► (prime 41) 2**41 (max digits used: 64) 2,199,023,255,552
term 117,832 ──► (prime 43) 2**43 (max digits used: 67) 8,796,093,022,208
term 152,026 ──► (prime 47) 2**47 (max digits used: 73) 140,737,488,355,328
term 215,385 ──► (prime 53) 2**53 (max digits used: 83) 9,007,199,254,740,992
term 293,376 ──► (prime 59) 2**59 (max digits used: 92) 576,460,752,303,423,488
term 327,021 ──► (prime 61) 2**61 (max digits used: 95) 2,305,843,009,213,693,952
term 428,554 ──► (prime 67) 2**67 (max digits used: 104) 147,573,952,589,676,412,928
term 507,520 ──► (prime 71) 2**71 (max digits used: 110) 2,361,183,241,434,822,606,848
term 555,695 ──► (prime 73) 2**73 (max digits used: 113) 9,444,732,965,739,290,427,392
term 700,064 ──► (prime 79) 2**79 (max digits used: 123) 604,462,909,807,314,587,353,088
term 808,332 ──► (prime 83) 2**83 (max digits used: 129) 9,671,406,556,917,033,397,649,408
term 989,527 ──► (prime 89) 2**89 (max digits used: 138) 618,970,019,642,690,137,449,562,112
term 1,273,491 ──► (prime 97) 2**97 (max digits used: 151) 158,456,325,028,528,675,187,087,900,672
term 1,434,367 ──► (prime 101) 2**101 (max digits used: 157) 2,535,301,200,456,458,802,993,406,410,752
term 1,530,214 ──► (prime 103) 2**103 (max digits used: 160) 10,141,204,801,825,835,211,973,625,643,008
term 1,710,924 ──► (prime 107) 2**107 (max digits used: 166) 162,259,276,829,213,363,391,578,010,288,128
term 1,818,255 ──► (prime 109) 2**109 (max digits used: 169) 649,037,107,316,853,453,566,312,041,152,512
term 2,019,963 ──► (prime 113) 2**113 (max digits used: 175) 10,384,593,717,069,655,257,060,992,658,440,192
term 2,833,090 ──► (prime 127) 2**127 (max digits used: 197) 170,141,183,460,469,231,731,687,303,715,884,105,728
term 3,104,686 ──► (prime 131) 2**131 (max digits used: 203) 2,722,258,935,367,507,707,706,996,859,454,145,691,648
term 3,546,321 ──► (prime 137) 2**137 (max digits used: 212) 174,224,571,863,520,493,293,247,799,005,065,324,265,472
term 3,720,786 ──► (prime 139) 2**139 (max digits used: 215) 696,898,287,454,081,973,172,991,196,020,261,297,061,888
term 4,549,719 ──► (prime 149) 2**149 (max digits used: 231) 713,623,846,352,979,940,529,142,984,724,747,568,191,373,312
term 4,755,582 ──► (prime 151) 2**151 (max digits used: 234) 2,854,495,385,411,919,762,116,571,938,898,990,272,765,493,248
term 5,329,875 ──► (prime 157) 2**157 (max digits used: 243) 182,687,704,666,362,864,775,460,604,089,535,377,456,991,567,872
term 5,958,404 ──► (prime 163) 2**163 (max digits used: 252) 11,692,013,098,647,223,345,629,478,661,730,264,157,247,460,343,808
term 6,400,898 ──► (prime 167) 2**167 (max digits used: 259) 187,072,209,578,355,573,530,071,658,587,684,226,515,959,365,500,928
term 7,120,509 ──► (prime 173) 2**173 (max digits used: 268) 11,972,621,413,014,756,705,924,586,149,611,790,497,021,399,392,059,392
term 7,868,448 ──► (prime 179) 2**179 (max digits used: 277) 766,247,770,432,944,429,179,173,513,575,154,591,809,369,561,091,801,088
term 8,164,153 ──► (prime 181) 2**181 (max digits used: 280) 3,064,991,081,731,777,716,716,694,054,300,618,367,237,478,244,367,204,352
term 9,541,986 ──► (prime 191) 2**191 (max digits used: 296) 3,138,550,867,693,340,381,917,894,711,603,833,208,051,177,722,232,017,256,448
term 9,878,163 ──► (prime 193) 2**193 (max digits used: 299) 12,554,203,470,773,361,527,671,578,846,415,332,832,204,710,888,928,069,025,792
term 10,494,775 ──► (prime 197) 2**197 (max digits used: 305) 200,867,255,532,373,784,442,745,261,542,645,325,315,275,374,222,849,104,412,672
term 10,852,158 ──► (prime 199) 2**199 (max digits used: 308) 803,469,022,129,495,137,770,981,046,170,581,301,261,101,496,891,396,417,650,688
term 12,871,594 ──► (prime 211) 2**211 (max digits used: 327) 3,291,009,114,642,412,084,309,938,365,114,701,009,965,471,731,267,159,726,697,218,048
term 15,137,114 ──► (prime 223) 2**223 (max digits used: 345) 13,479,973,333,575,319,897,333,507,543,509,815,336,818,572,211,270,286,240,551,805,124,608
term 15,956,646 ──► (prime 227) 2**227 (max digits used: 351) 215,679,573,337,205,118,357,336,120,696,157,045,389,097,155,380,324,579,848,828,881,993,728
term 16,429,799 ──► (prime 229) 2**229 (max digits used: 354) 862,718,293,348,820,473,429,344,482,784,628,181,556,388,621,521,298,319,395,315,527,974,912
term 17,293,373 ──► (prime 233) 2**233 (max digits used: 361) 13,803,492,693,581,127,574,869,511,724,554,050,904,902,217,944,340,773,110,325,048,447,598,592
term 18,633,402 ──► (prime 239) 2**239 (max digits used: 370) 883,423,532,389,192,164,791,648,750,371,459,257,913,741,948,437,809,479,060,803,100,646,309,888
term 19,157,411 ──► (prime 241) 2**241 (max digits used: 373) 3,533,694,129,556,768,659,166,595,001,485,837,031,654,967,793,751,237,916,243,212,402,585,239,552
term 21,564,310 ──► (prime 251) 2**251 (max digits used: 388) 3,618,502,788,666,131,106,986,593,281,521,497,120,414,687,020,801,267,626,233,049,500,247,285,301,248
term 23,157,731 ──► (prime 257) 2**257 (max digits used: 398) 231,584,178,474,632,390,847,141,970,017,375,815,706,539,969,331,281,128,078,915,168,015,826,259,279,872
term 24,805,778 ──► (prime 263) 2**263 (max digits used: 407) 14,821,387,422,376,473,014,217,086,081,112,052,205,218,558,037,201,992,197,050,570,753,012,880,593,911,808
term 26,506,125 ──► (prime 269) 2**269 (max digits used: 416) 948,568,795,032,094,272,909,893,509,191,171,341,133,987,714,380,927,500,611,236,528,192,824,358,010,355,712
term 27,168,588 ──► (prime 271) 2**271 (max digits used: 419) 3,794,275,180,128,377,091,639,574,036,764,685,364,535,950,857,523,710,002,444,946,112,771,297,432,041,422,848
term 28,973,145 ──► (prime 277) 2**277 (max digits used: 428) 242,833,611,528,216,133,864,932,738,352,939,863,330,300,854,881,517,440,156,476,551,217,363,035,650,651,062,272
term 30,230,537 ──► (prime 281) 2**281 (max digits used: 435) 3,885,337,784,451,458,141,838,923,813,647,037,813,284,813,678,104,279,042,503,624,819,477,808,570,410,416,996,352
term 30,952,920 ──► (prime 283) 2**283 (max digits used: 438) 15,541,351,137,805,832,567,355,695,254,588,151,253,139,254,712,417,116,170,014,499,277,911,234,281,641,667,985,408
term 34,284,307 ──► (prime 293) 2**293 (max digits used: 453) 15,914,343,565,113,172,548,972,231,940,698,266,883,214,596,825,515,126,958,094,847,260,581,103,904,401,068,017,057,792
term 39,303,996 ──► (prime 307) 2**307 (max digits used: 475) 260,740,604,970,814,219,042,361,048,116,400,404,614,587,954,389,239,840,081,425,977,517,360,806,369,707,098,391,474,864,128
term 40,844,960 ──► (prime 311) 2**311 (max digits used: 481) 4,171,849,679,533,027,504,677,776,769,862,406,473,833,407,270,227,837,441,302,815,640,277,772,901,915,313,574,263,597,826,048
term 41,728,501 ──► (prime 313) 2**313 (max digits used: 484) 16,687,398,718,132,110,018,711,107,079,449,625,895,333,629,080,911,349,765,211,262,561,111,091,607,661,254,297,054,391,304,192
term 43,329,639 ──► (prime 317) 2**317 (max digits used: 490) 266,998,379,490,113,760,299,377,713,271,194,014,325,338,065,294,581,596,243,380,200,977,777,465,722,580,068,752,870,260,867,072
term 49,260,306 ──► (prime 331) 2**331 (max digits used: 512) 4,374,501,449,566,023,848,745,004,454,235,242,730,706,338,861,786,424,872,851,541,212,819,905,998,398,751,846,447,026,354,046,107,648
...
(some output elided.)
...
</pre>
Output note: There are intermediary numbers (that aren't powers of two) that are hundreds of digits long. <br><br>
=={{header|RPL}}==
≪ → text
≪ "{'" 1 text SIZE '''FOR''' j
text j DUP SUB
'''IF''' DUP " " == '''THEN''' DROP "' '" '''END''' +
'''NEXT'''
"'}" + STR→
≫ ≫ '<span style="color:blue">PRECOMPIL</span>' STO <span style="color:grey">@ ( "fractions" → { 'fractions' } )</span>
≪ SWAP 20 → prog steps
≪ {} SWAP
1 steps '''FOR''' n
1 CF
1 prog SIZE '''FOR''' j
prog j GET OVER * EVAL RND
'''IF''' DUP FP '''THEN''' DROP '''ELSE'''
SWAP DROP SWAP OVER + SWAP
prog SIZE 'j' STO 1 SF '''END'''
'''NEXT'''
'''IF''' 1 FC?C '''THEN''' steps 'n' STO '''END'''
'''NEXT''' DROP
≫ ≫ '<span style="color:blue">RUN20</span>' STO <span style="color:grey">@ ( { 'fractions' } n → { results } )</span>
"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" <span style="color:blue">PRECOMPIL</span>
2 <span style="color:blue">RUN20</span>
{{out}}
<pre>
1: { 15 825 725 1925 2275 425 390 330 290 770 910 170 156 132 116 308 364 68 4 30 }
</pre>
=={{header|Ruby}}==
<
FractalProgram = ar.map(&:to_r) #=> array of rationals
Line 3,002 ⟶ 4,328:
# demo
p Runner.take(20).map(&:numerator)
p prime_generator.take(20)</
{{Out}}
Line 3,011 ⟶ 4,337:
=={{header|Scala}}==
<
val program = 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")
val expect = List(2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132)
Line 3,034 ⟶ 4,360:
}
}
}</
=={{header|Scheme}}==
Scheme naturally handles fractions, translating to integers as required.
The first part of the code translates from a string representation, as required, but equally the user could type the list of fractions in directly as a list.
{{libheader|Scheme/SRFIs}}
Similar to Python implementation of generating primes, the power of 2 is detected by first converting the number to binary representation, and check if it has only 1 "1" bit.
<syntaxhighlight lang="scheme">(import (scheme base)
(scheme inexact)
(scheme read)
(scheme write
(srfi 13)) ;; for string-length and string-ref
(define *string-fractions* ; string input of fractions
Line 3,082 ⟶ 4,408:
;; Extra Credit: derive first 20 prime numbers
(define (generate-primes target-number initial-n)
(define (is-power-of-two? n) ; a binary with only 1 "1" bit is a power of 2
(
(else
(let loop ((i 0) (acc 0) (binary-str (number->string n 2)))
(cond ((= i (string-length binary-str))
#t)
((and (eq? (string-ref binary-str i) #\1) (= 1 acc))
#f)
((eq? (string-ref binary-str i) #\1)
(loop (+ 1 i) (+ 1 acc) binary-str))
(else
(loop (+ 1 i) acc binary-str)))))))
(define (extract-prime n) ; just gets the number of zeroes in binary
(let ((binary-str (number->string n 2)))
(- (string-length binary-str) 1)))
;
(let loop ((count 0)
Line 3,103 ⟶ 4,440:
(display "Primes:\n")
(generate-primes 20 2) ; create first 20 primes</syntaxhighlight>
{{out}}
<pre>Task: 2 15 825 725 1925 2275 425 390 330 290 770 910 170 156 132 116 308 364 68 4
Primes:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71
</pre>
=={{header|Seed7}}==
<
include "rational.s7i";
Line 3,150 ⟶ 4,483:
end for;
writeln;
end func;</
{{out}}
Line 3,158 ⟶ 4,491:
Program to compute prime numbers with fractran (The program has no limit, use CTRL-C to terminate it):
<
include "bigrat.s7i";
Line 3,186 ⟶ 4,519:
begin
fractran(2_, program);
end func;</
{{out}}
Line 3,220 ⟶ 4,553:
=={{header|Sidef}}==
{{trans|Ruby}}
<
const FractalProgram = str.split(',').map{.num} #=> array of rationals
Line 3,247 ⟶ 4,580:
prime_generator(20, {|n| print (n, ' ') })
print "\n"</
{{out}}
<pre>
Line 3,256 ⟶ 4,589:
=={{header|Tcl}}==
{{works with|Tcl|8.6}}
<
oo::class create Fractran {
Line 3,304 ⟶ 4,637:
77/19 1/17 11/13 13/11 15/14 15/2 55/1
}]
puts [$ft execute 2]</
{{out}}
<pre>
Line 3,310 ⟶ 4,643:
</pre>
You can just collect powers of 2 by monkey-patching in something like this:
<
set co [coroutine [incr nco] my Generate 2]
set pows {}
Line 3,321 ⟶ 4,654:
return $pows
}
puts [$ft pow2 10]</
Which will then produce this additional output:
<pre>
2 4 8 32 128 2048 8192 131072 524288 8388608
</pre>
=={{header|TI-83 BASIC}}==
{{works with|TI-83 BASIC|TI-84Plus 2.55MP}}
<syntaxhighlight lang="ti83b">100->T
2->N
{17,78,19,23,29,77,95,77, 1,11,13,15,15,55}->LA
{91,85,51,38,33,29,23,19,17,13,11,14, 2, 1}->LB
Dim(LA)->U
T->Dim(LC)
For(I,1,T)
1->J: 1->F
While J<=U and F=1
If remainder(N,LB(J))=0
Then
Disp N
N->LC(I)
iPart(N/LB(J))*LA(J)->N
0->F
End
J+1->J
End
End</syntaxhighlight>
Note:
-> stands for Store symbol
L stands for List symbol in LA,LB,LC
{{out}}
<pre>
2
15
825
725
1925
2275
425
390
330
290
...
2128
1288
</pre>
=={{header|VBA}}==
This implementations follows the Wikipedia description of [[wp:FRACTRAN|FRACTRAN]]. There are test, decrement and increment instructions on an array of variables which are the exponents of the prime factors of the argument, which are the only instructions used to run the program with the function run, or go through it step by step with the function steps. An auxiliary factor function is used to compile the FRACTRAN program.
<syntaxhighlight lang="vb">Option Base 1
Public prime As Variant
Public nf As New Collection
Public df As New Collection
Const halt = 20
Private Sub init()
prime = [{2,3,5,7,11,13,17,19,23,29,31}]
End Sub
Private Function factor(f As Long) As Variant
Dim result(10) As Integer
Dim i As Integer: i = 1
Do While f > 1
Do While f Mod prime(i) = 0
f = f \ prime(i)
result(i) = result(i) + 1
Loop
i = i + 1
Loop
factor = result
End Function
Private Function decrement(ByVal a As Variant, b As Variant) As Variant
For i = LBound(a) To UBound(a)
a(i) = a(i) - b(i)
Next i
decrement = a
End Function
Private Function increment(ByVal a As Variant, b As Variant) As Variant
For i = LBound(a) To UBound(a)
a(i) = a(i) + b(i)
Next i
increment = a
End Function
Private Function test(a As Variant, b As Variant)
flag = True
For i = LBound(a) To UBound(a)
If a(i) < b(i) Then
flag = False
Exit For
End If
Next i
test = flag
End Function
Private Function unfactor(x As Variant) As Long
result = 1
For i = LBound(x) To UBound(x)
result = result * prime(i) ^ x(i)
Next i
unfactor = result
End Function
Private Sub compile(program As String)
program = Replace(program, " ", "")
programlist = Split(program, ",")
For Each instruction In programlist
parts = Split(instruction, "/")
nf.Add factor(Val(parts(0)))
df.Add factor(Val(parts(1)))
Next instruction
End Sub
Private Function run(x As Long) As Variant
n = factor(x)
counter = 0
Do While True
For i = 1 To df.Count
If test(n, df(i)) Then
n = increment(decrement(n, df(i)), nf(i))
Exit For
End If
Next i
Debug.Print unfactor(n);
counter = counter + 1
If num = 31 Or counter >= halt Then Exit Do
Loop
Debug.Print
run = n
End Function
Private Function steps(x As Variant) As Variant
'expects x=factor(n)
For i = 1 To df.Count
If test(x, df(i)) Then
x = increment(decrement(x, df(i)), nf(i))
Exit For
End If
Next i
steps = x
End Function
Private Function is_power_of_2(x As Variant) As Boolean
flag = True
For i = LBound(x) + 1 To UBound(x)
If x(i) > 0 Then
flag = False
Exit For
End If
Next i
is_power_of_2 = flag
End Function
Private Function filter_primes(x As Long, max As Integer) As Long
n = factor(x)
i = 0: iterations = 0
Do While i < max
If is_power_of_2(steps(n)) Then
Debug.Print n(1);
i = i + 1
End If
iterations = iterations + 1
Loop
Debug.Print
filter_primes = iterations
End Function
Public Sub main()
init
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")
Debug.Print "First 20 results:"
output = run(2)
Debug.Print "First 30 primes:"
Debug.Print "after"; filter_primes(2, 30); "iterations."
End Sub</syntaxhighlight>{{out}}
<pre>First 20 results:
15 825 725 1925 2275 425 390 330 290 770 910 170 156 132 116 308 364 68 4 30
First 30 primes:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113
after 2019962 iterations.</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-big}}
Extra credit is glacially slow. We just find the first 10 primes which takes about 85 seconds.
<syntaxhighlight lang="wren">import "./big" for BigInt, BigRat
var isPowerOfTwo = Fn.new { |bi| bi & (bi - BigInt.one) == BigInt.zero }
var fractran = Fn.new { |program, n, limit, primesOnly|
var fractions = program.split(" ").where { |s| s != "" }
.map { |s| BigRat.fromRationalString(s) }
.toList
var results = []
if (!primesOnly) results.add(n)
var nn = BigInt.new(n)
while (results.count < limit) {
var fracs = fractions.where { |f| (f * nn).isInteger }.toList
if (fracs.count == 0) break
var frac = fracs[0]
nn = nn * frac.num / frac.den
if (!primesOnly) {
results.add(nn.toSmall)
} else if (primesOnly && isPowerOfTwo.call(nn)) {
var prime = (nn.toNum.log / 2.log).floor
results.add(prime)
}
}
return results
}
var program = "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"
System.print("First twenty numbers:")
System.print(fractran.call(program, 2, 20, false))
System.print("\nFirst ten primes:")
System.print(fractran.call(program, 2, 10, true))</syntaxhighlight>
{{out}}
<pre>
First twenty numbers:
[2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4]
First ten primes:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
</pre>
=={{header|zkl}}==
<
"11/13, 13/11, 15/14, 15/2, 55/1";
fcn fractranW(n,fracsAsOneBigString){ //-->Walker (iterator)
Line 3,342 ⟶ 4,885:
}
}.fp(Ref(n),fracs))
}</
<
{{out}}
<pre>
Line 3,349 ⟶ 4,892:
</pre>
{{trans|Python}}
<
fcn fractranPrimes{
foreach n,fr in ([1..].zip(fractranW(BN(2),fracs))){
Line 3,359 ⟶ 4,902:
}
}
fractranPrimes();</
{{out}}
<pre>
| |||