Function Repository Resource:

Fractran

Source Notebook

Interpret the FRACTRAN esoteric programming language

Contributed by: Daniel Sanchez and Jan Mangaldan

ResourceFunction["Fractran"][prog,n]

runs the FRACTRAN program prog on the integer n.

Details and Options

FRACTRAN is an esoteric programming language invented by the mathematician John H. Conway.
The result of a FRACTRAN execution is a list of integers.
A FRACTRAN program can have one of the following forms:
FRACTRAN-1 program{f1,f2,}where each fi is a positive fraction
FRACTRAN-n program{,{fl1l1,fl2l2,},}where flm are positive fractions and each lm is an integer between 1 and n (the length of the list)
The FRACTRAN-1 program ResourceFunction["Fractran"][{f1,f2,,fi,},n] repeatedly multiplies the integer at any stage (initially n) against the earliest fraction fi in the list that yields an integer product, stopping the execution when there is no such fi.
The FRACTRAN-n program ResourceFunction["Fractran"][{,{fl1l1,fl2l2,},},n] repeatedly multiplies the integer at any stage (initially n) against the earliest fraction flm in line l (initially 1) that yields an integer product, then proceeds to the line indicated by lm, stopping the execution when there is no such flm.
The first element of the resulting list is always the starting integer n.
If ResourceFunction["Fractran"] terminates early, the last element of the resulting list is 0.
ResourceFunction["Fractran"] has the following options:
MaxIterationsInfinitymaximum number of iterations
"MaxResults"Infinitymaximum number of integers in the result
"SelectionCriterion"Automatictest to determine whether an integer should be included in the result
"ShowProgramLines"Falseif set to True, show the program line currently being executed
The FRACTRAN language can be considered a type of register machine where: 1) The integer n stores the contents of the registers in the exponents of prime factors of n. For example 34992 = 24×37 represents a register state in which the register "2" holds the value 4 and the register "3" the value 7. 2) Each positive fraction fi in a program represents an instruction that operates on the integer n. The instruction is executed only if fi × n yields an integer product, otherwise, a negative value will be stored in the register state n. For example, the fraction can operate on 24×37 resulting in 23×38, but not on 311 as the final register state would be 2-1×312.

Examples

Basic Examples (3) 

Run a simple FRACTRAN program representing integer addition, where given an input of the form 2a3b the program will have a + b encoded as 3a+b in the last positive integer of the resulting list:

In[1]:=
ResourceFunction["Fractran"][{3/2}, 2^4 3^7]
Out[1]=

Decode the answer:

In[2]:=
Log[3, %[[-2]]]
Out[2]=

The following program represents integer subtraction, where given the input of the form 2a3b the program will have a - b encoded as 2a-b (for a>b) in the last positive integer of the resulting list:

In[3]:=
Function[{a, b}, BitLength[ResourceFunction["Fractran"][{1/(2 3)}, 2^a 3^b][[-2]]] - 1][20, 18]
Out[3]=

Use John Conway's PRIMEGAME program to compute prime numbers encoded as powers of 2 if the program is started at 2:

In[4]:=
primeGame = {17/91, 78/85, 19/51, 23/38, 29/33, 77/29, 95/23, 77/19, 1/17, 11/13, 13/11, 15/2, 1/7, 55};
Log2@Rest@
  ResourceFunction["Fractran"][primeGame, 2, MaxResults -> 10, SelectionCriterion -> IntegerQ@*Log2]
Out[64]=
In[65]:=
% === Array[Prime, 10]
Out[65]=

Scope (2) 

FRACTRAN-1 program (1) 

Define addition by using the FRACTRAN-1 program:

In[66]:=
fractranAddition[a_, b_] := Log[3, ResourceFunction["Fractran"][{3/2}, 2^a 3^b][[-2]]]
Table[{StringTemplate["`1` + `2` = `3`"][a, b, fractranAddition[a, b]]}, {a, 5, 10}, {b, 10, 15}] // TableForm
Out[67]=

FRACTRAN-n program (1) 

The following FRACTRAN-n program corresponds to multiplication, where given the input of the form 3a7b the program will stop when 2a b is computed:

In[68]:=
multiplicationProgram = {
   {1/7 -> 2, 1/3 -> 1}, (* decrement the contents of Subscript[r, 7]
    by 1 and jump to line 2; clear Subscript[r, 3] *)
   {(5 2)/3 -> 2, 1/1 -> 3}, (* move the contents of Subscript[r, 3]
    to Subscript[r, 2] and Subscript[r, 5]; jump to line 3 *)
   {3/5 -> 3, 1/1 -> 1}}; (* restore the contents of Subscript[r, 3] from Subscript[r, 5]; loop back to line 1 *)
fractranMultiplication[a_, b_] := Log2@ResourceFunction["Fractran"][multiplicationProgram, 3^a 7^b][[-2]]
Table[{StringTemplate["`1` * `2` = `3`"][a, b, fractranMultiplication[a, b]]}, {a, 5, 10}, {b, 10, 15}] // TableForm
Out[69]=

Options (6) 

MaxIterations (1) 

MaxIterations specifies the maximum number of steps to take in running the Fractran program:

In[70]:=
Table[ResourceFunction["Fractran"][{
Rational[365, 46], 
Rational[29, 161], 
Rational[79, 575], 
Rational[679, 451], 
Rational[3159, 413], 
Rational[83, 407], 
Rational[473, 371], 
Rational[638, 355], 
Rational[434, 335], 
Rational[89, 235], 
Rational[17, 209], 
Rational[79, 122], 
Rational[31, 183], 
Rational[41, 115], 
Rational[517, 89], 
Rational[111, 83], 
Rational[305, 79], 
Rational[23, 73], 
Rational[73, 71], 
Rational[61, 67], 
Rational[37, 61], 
Rational[19, 59], 
Rational[89, 57], 
Rational[41, 53], 
Rational[833, 47], 
Rational[53, 43], 
Rational[86, 41], 
Rational[13, 38], 
Rational[23, 37], 
Rational[67, 31], 
Rational[71, 29], 
Rational[83, 19], 
Rational[475, 17], 
Rational[59, 13], 
Rational[41, 291], 
Rational[1, 7], 
Rational[1, 11], 
Rational[1, 1024], 
Rational[1, 97], 89}, 2, MaxIterations -> i] // Length, {i, 10, 100, 10}]
Out[70]=

MaxResults (2) 

"MaxResults" specifies the maximum number of integers to be returned, excluding the initial condition:

In[71]:=
ResourceFunction["Fractran"][{
Rational[7, 3], 
Rational[99, 98], 
Rational[13, 49], 
Rational[39, 35], 
Rational[36, 91], 
Rational[10, 143], 
Rational[49, 13], 
Rational[7, 11], 
Rational[1, 2], 91}, 10, "MaxResults" -> 5, MaxIterations -> Infinity]
Out[72]=

This option is most commonly used with "SelectionCriterion":

In[73]:=
ResourceFunction["Fractran"][{
Rational[7, 3], 
Rational[99, 98], 
Rational[13, 49], 
Rational[39, 35], 
Rational[36, 91], 
Rational[10, 143], 
Rational[49, 13], 
Rational[7, 11], 
Rational[1, 2], 91}, 10, "SelectionCriterion" -> IntegerQ@*Log10, "MaxResults" -> 5]
Out[74]=

SelectionCriterion (1) 

For "SelectionCriterion" crit, all integers ni of the resulting list for which crit[ni] is True are picked:

In[75]:=
ResourceFunction["Fractran"][{
Rational[7, 3], 
Rational[99, 98], 
Rational[13, 49], 
Rational[39, 35], 
Rational[36, 91], 
Rational[10, 143], 
Rational[49, 13], 
Rational[7, 11], 
Rational[1, 2], 91}, 10, "SelectionCriterion" -> IntegerQ@*Log10, MaxIterations -> 1000]
Out[76]=

ShowProgramLines (2) 

If "ShowProgramLines" set to True, append the program line currently being executed:

In[77]:=
ResourceFunction[
 "Fractran"][{{Rational[1, 7] -> 2, Rational[1, 3] -> 1}, {Rational[10, 3] -> 2, 1 -> 3}, {Rational[3, 5] -> 3, 1 -> 1}}, 3^5 7^4, ShowProgramLines -> True]
Out[77]=

This option is mainly used alongside FRACTRAN-n programs. For FRACTRAN-1 programs, the line shown is always 1:

In[78]:=
ResourceFunction["Fractran"][{1/(2 3)}, 2^8 3^3, ShowProgramLines -> True]
Out[78]=

Possible Issues (1) 

The default value of the MaxIterations is Infinity and as such, special care should be taken when the Fractran program does not halt:

In[79]:=
TimeConstrained[ResourceFunction["Fractran"][{
Rational[17, 91], 
Rational[78, 85], 
Rational[19, 51], 
Rational[23, 38], 
Rational[29, 33], 
Rational[77, 29], 
Rational[95, 23], 
Rational[77, 19], 
Rational[1, 17], 
Rational[11, 13], 
Rational[13, 11], 
Rational[15, 2], 
Rational[1, 7], 55}, 2], 5]
Out[79]=

Neat Examples (2) 

Kilminster's prime number generator:

In[80]:=
primeKilminster = {3/11, 847/45, 143/6, 7/3, 10/91, 3/7, 36/325, 1/2, 36/5};
ResourceFunction["Fractran"][primeKilminster, 10, SelectionCriterion -> IntegerQ@*Log10, MaxResults -> 10]
Out[81]=

Use IntegerLength to get the result:

In[82]:=
IntegerLength[Rest[%]] - 1
Out[82]=

Calculate the Hamming weight H[a] of the binary expansion of a, where if given the input 2a its output is 13H[a]:

In[83]:=
hammingDistance = {(3 11)/(2^2 5), 5/11, 13/(2 5), 1/5, 2/3, (2 5)/7, 7/2};
fracHammingWeight[a_Integer] := Log[13, ResourceFunction["Fractran"][hammingDistance, 2^a][[-2]]]
fracHammingWeight[29]
Out[84]=

Compare it with a custom Hamming weight defined in terms of HammingDistance:

In[85]:=
wlHammingWeight[a_Integer] := HammingDistance[IntegerDigits[a, 2], ConstantArray[0, IntegerLength[a, 2]]]
And @@ Table[fracHammingWeight[i] === wlHammingWeight[i], {i, 1, 32}]
Out[86]=

Publisher

Daniel Sanchez

Requirements

Wolfram Language 12.2 (December 2020) or above

Version History

  • 1.0.0 – 18 January 2021

Source Metadata

Related Resources

License Information