How to resolve the algorithm Fractran step by step in the Erlang programming language

Published on 12 May 2024 09:40 PM
#Erlang

How to resolve the algorithm Fractran step by step in the Erlang programming language

Table of Contents

Problem Statement

FRACTRAN is a Turing-complete esoteric programming language invented by the mathematician John Horton Conway. A FRACTRAN program is an ordered list of positive fractions

P

(

f

1

,

f

2

, … ,

f

m

)

{\displaystyle P=(f_{1},f_{2},\ldots ,f_{m})}

, together with an initial positive integer input

n

{\displaystyle n}

.

The program is run by updating the integer

n

{\displaystyle n}

as follows:

Conway gave a program for primes in FRACTRAN: Starting with

n

2

{\displaystyle n=2}

, this FRACTRAN program will change

n

{\displaystyle n}

to

15

2 × ( 15

/

2 )

{\displaystyle 15=2\times (15/2)}

, then

825

15 × ( 55

/

1 )

{\displaystyle 825=15\times (55/1)}

, generating the following sequence of integers: After 2, this sequence contains the following powers of 2: which are the prime powers of 2.

Write a program that reads a list of fractions in a natural format from the keyboard or from a string, to parse it into a sequence of fractions (i.e. two integers), and runs the FRACTRAN starting from a provided integer, writing the result at each step.
It is also required that the number of steps is limited (by a parameter easy to find).

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

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

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Fractran step by step in the Erlang programming language

Source code in the erlang programming language

#! /usr/bin/escript

-mode(native).
-import(lists, [map/2, reverse/1]).

binary_to_ratio(B) ->
    {match, [_, Num, Den]} = re:run(B, "([0-9]+)/([0-9]+)"),
    {binary_to_integer(binary:part(B, Num)),
     binary_to_integer(binary:part(B, Den))}.

load(Program) ->
    map(fun binary_to_ratio/1, re:split(Program, "[ ]+")).

step(_, []) -> halt;
step(N, [F|Fs]) ->
    {P, Q} = mulrat(F, {N, 1}),
    case Q of
        1 -> P;
        _ -> step(N, Fs)
    end.

exec(K, N, Program) -> reverse(exec(K - 1, N, fun (_) -> true end, Program, [N])).
exec(K, N, Pred, Program) -> reverse(exec(K - 1, N, Pred, Program, [N])).

exec(0, _, _, _, Steps) -> Steps;
exec(K, N, Pred, Program, Steps) ->
    case step(N, Program) of
        halt -> Steps;
        M -> case Pred(M) of 
                true  -> exec(K - 1, M, Pred, Program, [M|Steps]);
                false -> exec(K, M, Pred, Program, Steps)
            end
    end.


is_pow2(N) -> N band (N - 1) =:= 0.

lowbit(N) -> lowbit(N, 0).
lowbit(N, K) ->
    case N band 1 of
        0 -> lowbit(N bsr 1, K + 1);
        1 -> K
    end.

main(_) ->
    PrimeGen = 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"),
    io:format("The first few states of the Fractran prime automaton are: ~p~n~n", [exec(20, 2, PrimeGen)]),
    io:format("The first few primes are: ~p~n", [tl(map(fun lowbit/1, exec(26, 2, fun is_pow2/1, PrimeGen)))]).


% rational multiplication

mulrat({A, B}, {C, D}) ->
    {P, Q} = {A*C, B*D},
    G = gcd(P, Q),
    {P div G, Q div G}.

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

You may also check:How to resolve the algorithm Show ASCII table step by step in the FutureBasic programming language
You may also check:How to resolve the algorithm Semordnilap step by step in the Lasso programming language
You may also check:How to resolve the algorithm Halt and catch fire step by step in the 6502 Assembly programming language
You may also check:How to resolve the algorithm Random number generator (device) step by step in the Ring programming language
You may also check:How to resolve the algorithm Pascal matrix generation step by step in the Delphi programming language