Fractran: Difference between revisions

{{trans|D}}

V fracts = prog.split(‘ ’).map(p -> p.split(‘/’).map(i -> Int(i)))

[Float] r

R r

{{out}}

=={{header|360 Assembly}}==

FRACTRAN CSECT

USING FRACTRAN,R13 base register

XDEC DS CL12 temp

REGEQU

{{out}}

<pre>

=={{header|Ada}}==

procedure Fractan is

2, 15);

-- output is "0: 2 1: 15 2: 825 3: 725 ... 14: 132 15: 116"

{{out}}

=={{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

print( ( whole( pos, -12 ) + " " + whole( power of 2, -6 ) + " (" + whole( n OF pf, 0 ) + ")", newline ) )

FI

{{out}}

<pre>

=={{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"

}

break

{{out}}

<pre>0: 2

the "factor" command allows one to decrypt the data. For example, the program below computes the product of a and b, entered as 2^a and 3^b, the product being 5^a×b. 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"

let "t=$t+1"

done

If at the beginning n=72=2³×3² (to compute 3×2), the steps of the computation look like this:

=={{header|Batch File}}==

setlocal enabledelayedexpansion

echo.

pause

{{Out}}

<pre>Input:

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\.<

{{out}}

<code>Fractran</code> performs a single iteration of fractran on a given input, list of numerators and list of denominators.

# Helpers

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

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

=={{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}

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>

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>

return 0;

=={{header|C++}}==

#include <iostream>

#include <sstream>

return 0;

}

{{out}}

<pre>

=={{header|Common Lisp}}==

(lambda ()

(prog1

for next = (funcall fractran-instance)

until (null next)

{{out}}

===Simple Version===

{{trans|Java}}

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

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

===Lazy Version===

struct Fractran {

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>

{{libheader| System.RegularExpressions}}

{{Trans|Java}}

program FractranTest;

TFractan.Create(DATA, 2).Free;

Readln;

{{out}}

<pre>

=={{header|Elixir}}==

{{trans|Erlang}}

use Bitwise

|> Enum.map(&Fractran.lowbit/1)

|> tl

{{out}}

=={{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).

gcd(A, 0) -> A;

gcd(A, B) -> gcd(B, A rem B).

{{out}}

<pre>

=={{header|Factor}}==

prettyprint sequences splitting ;

IN: rosetta-code.fractran

2bi ;

{{out}}

<pre>

=={{header|Fermat}}==

;{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}

[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 )];

{{out}}<pre>

2

===The Code===

So much for multi-pass compilers!

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.

END DO !The next step.

END !Whee!

===The Results===

28 1: 14875

</pre>

IT = FRACTRAN(N,P,Q,L) !Do it!

IF (POPCNT(N).EQ.1) WRITE (6,11) I,IT,N !Show it!

END IF !So much for overflow.

END DO !The next step.

Leads to the following output:

<pre>

===Revised Code===

USE PRIMEBAG !This is a common need.

INTEGER LASTP,ENUFF !Some size allowances.

Complete!

END !Whee!

===Revised Results===

100 7: 3 1 1 1

</pre>

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?

Output:

=={{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

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre>2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116

=={{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 (

}

exec(p, &n, limit)

{{out|Command line usage, with program compiled as "ft"}}

<pre>

Extra credit: This invokes above program with appropriate arguments,

and processes the output to obtain the 20 primes.

import (

}

fmt.Println()

{{out}}

<pre>

=={{header|Haskell}}==

===Running the program===

import Data.Ratio (Ratio, (%), denominator)

case find (\f -> n `mod` denominator f == 0) fracts of

Nothing -> []

Example:

===Reading the program===

Additional import

readProgram = map (toFrac . splitOn "/") . splitOn ","

Example of running the program:

===Generation of primes===

Additional import

primes = mapMaybe log2 $ fractran prog 2

where

, 55 % 1

]

<pre>λ> take 20 primes

Works in both languages:

procedure main(A)

}

write()

{{out}}

===Hybrid version===

'''Solution:'''

'''Example:'''

taskstr fractran15 2

===Tacit version===

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),

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'''

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),

'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

primes is also a stateless point-free functional,

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,

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,

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,

=={{header|Java}}==

import java.util.regex.Matcher;

import java.util.regex.Pattern;

System.out.println();

}

=={{header|JavaScript}}==

===Imperative===

function compile(prog, numArr, denArr) {

let regex = /\s*(\d*)\s*\/\s*(\d*)\s*(.*)/m;

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);

===Functional===

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';

// MAIN ---

return main();

{{Out}}

<pre>"First fifteen steps:" -> [2,15,825,725,1925,2275,425,390,330,290,770,910,170,156,132]

=={{header|Julia}}==

{{works with|Julia|0.6}}

rst = zeros(BigInt, steplim)

for i in 1:steplim

end

n = fractran(n, fracs, 2)[2]

{{output}}

=={{header|Kotlin}}==

import java.math.BigInteger

println("\nFirst twenty primes:")

println(fractran(program, 2, 20, true))

{{out}}

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;

n = newlist[[truepositions[[1, 1]]]]; j++;

]

{{out}}

<pre>0: 2

Here is a different solution using a functional approach:

fractran[

program : {__ ? (Element[#, PositiveRationals] &)}, (* list of positive fractions *)

$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]

{{out}}

Extract the first 20 prime numbers encoded as powers of 2:

Select[IntegerQ] @ Log2[fractran[$PRIMEGAME, 2, 500000]]

{{out}}

<pre>{1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67}</pre>

We provide a general function to run any Fractran program and a specialized iterator to find prime numbers.

import strutils

import bignum

for val in primes(20):

echo val

{{out}}

With this algorithm, we no longer need big numbers. To avoid overflow, value at each step is displayed using

its decomposition in prime factors.

import algorithm

import sequtils

echo "\nFirst twenty prime numbers:"

findPrimes(20)

{{out}}

=={{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 () =

let num = get_input () in

let prog = read_program () in

The program

{{Works with|PARI/GP|2.7.4 and above}}

\\ FRACTRAN

\\ 4/27/16 aev

print(fractran(2,v,15));

}

{{Output}}

This makes the fact that it's a prime-number-generating program much clearer.

use warnings;

use Math::BigRat;

print "\n";

If you uncomment the <pre>#print $n</pre>, it will print all the steps.

Division (to whole integer) is performed simply by subtracting the corresponding powers, as above not possible if any would be negative.

<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: #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>

{{out}}

<pre>

=={{header|Prolog}}==

load(Program, Fractions) :-

re_split("[ ]+", Program, Split), odd_items(Split, TextualFractions),

?- main.

{{Out}}

<pre>

=={{header|Python}}==

===Python: Generate series from a fractran program===

def fractran(n, fstring='17 / 91, 78 / 85, 19 / 51, 23 / 38, 29 / 33,'

n, m = 2, 15

print('First %i members of fractran(%i):\n ' % (m, n) +

{{out}}

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

from fractran import fractran

if __name__ == '__main__':

for (prime, i), j in zip(fractran_primes(), range(15)):

{{out}}

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.

[ 1 & not ] is even ( n --> b )

program release

{{out}}

=={{header|Racket}}==

{{trans|D}} Simple version, without sequences.

(define (displaysp x)

"13 / 11, 15 / 14, 15 / 2, 55 / 1")))

{{out}}

<pre>First 15 members of fractran(2):

{{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.

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

{{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.

2, { first Int, map (* * $_).narrow, @program } ... 0

}

15/14 15/2 55/1> {

say $++, "\t", .msb, "\t", $_ if 1 +< .msb == $_;

{{out}}

<pre>

=={{header|Red}}==

inp: ask "please enter list of fractions, or input file name: "

if l = index? code [halt]

]

{{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

Programming note: &nbsp; extra blanks can be inserted in the fractions before and/or after the solidus &nbsp; ['''<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*/

exit 0 /*stick a fork in it, we're all done. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

{{out|output|text=&nbsp; when using the default input:}}

<pre style="height:63ex">

===showing prime numbers===

Programming note: &nbsp; if the number of terms specified (the 2^nd argument) is negative, then only powers of two are displayed.

numeric digits 999; d= digits(); w= length(d) /*be able to handle gihugeic numbers. */

parse arg N terms fracs /*obtain optional arguments from the CL*/

exit 0 /*stick a fork in it, we're all done. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

{{out|output|text=&nbsp; when using the input (negative fifty million) of: &nbsp; &nbsp; <tt> , &nbsp; -50000000 </tt>}}

<pre>

=={{header|Ruby}}==

FractalProgram = ar.map(&:to_r) #=> array of rationals

# demo

p Runner.take(20).map(&:numerator)

{{Out}}

=={{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)

}

}

=={{header|Scheme}}==

{{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.

(scheme inexact)

(scheme read)

(display "Primes:\n")

{{out}}

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

=={{header|Seed7}}==

include "rational.s7i";

end for;

writeln;

{{out}}

Program to compute prime numbers with fractran (The program has no limit, use CTRL-C to terminate it):

include "bigrat.s7i";

begin

fractran(2_, program);

{{out}}

=={{header|Sidef}}==

{{trans|Ruby}}

const FractalProgram = str.split(',').map{.num} #=> array of rationals

prime_generator(20, {|n| print (n, ' ') })

{{out}}

<pre>

=={{header|Tcl}}==

{{works with|Tcl|8.6}}

oo::class create Fractran {

77/19 1/17 11/13 13/11 15/14 15/2 55/1

}]

{{out}}

<pre>

</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 {}

return $pows

}

Which will then produce this additional output:

<pre>

=={{header|TI-83 BASIC}}==

{{works with|TI-83 BASIC|TI-84Plus 2.55MP}}

2->N

{17,78,19,23,29,77,95,77, 1,11,13,15,15,55}->LA

J+1->J

End

Note:

-> stands for Store symbol

=={{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.

Public prime As Variant

Public nf As New Collection

Debug.Print "First 30 primes:"

Debug.Print "after"; filter_primes(2, 30); "iterations."

<pre>First 20 results:

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

{{libheader|Wren-big}}

Extra credit is glacially slow. We just find the first 10 primes which takes about 85 seconds.

var isPowerOfTwo = Fn.new { |bi| bi & (bi - BigInt.one) == BigInt.zero }

System.print(fractran.call(program, 2, 20, false))

System.print("\nFirst ten primes:")

{{out}}

=={{header|zkl}}==

"11/13, 13/11, 15/14, 15/2, 55/1";

fcn fractranW(n,fracsAsOneBigString){ //-->Walker (iterator)

}

}.fp(Ref(n),fracs))

{{out}}

<pre>

</pre>

{{trans|Python}}

fcn fractranPrimes{

foreach n,fr in ([1..].zip(fractranW(BN(2),fracs))){

}

}

{{out}}

<pre>