# Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

Interpret the FRACTRAN esoteric programming language

Contributed by:
Daniel Sanchez and Jan Mangaldan

ResourceFunction["Fractran"][ runs the FRACTRAN program |

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 | {f_{1},f_{2},…} | where each f_{i} is a positive fraction |

FRACTRAN-n program | {…,{f_{l1}→l_{1},f_{l2}→l_{2},…},…} | where f_{lm} are positive fractions and each l_{m} is an integer between 1 and n (the length of the list) |

The FRACTRAN-1 program ResourceFunction["Fractran"][{*f*_{1},*f*_{2},…,*f*_{i},…},*n*] repeatedly multiplies the integer at any stage (initially *n*) against the earliest fraction *f*_{i} in the list that yields an integer product, stopping the execution when there is no such *f*_{i}.

The FRACTRAN-*n* program ResourceFunction["Fractran"][{…,{*f*_{l1}→*l*_{1},*f*_{l2}→*l*_{2},…},…},*n*] repeatedly multiplies the integer at any stage (initially *n*) against the earliest fraction *f*_{lm} in line *l* (initially 1) that yields an integer product, then proceeds to the line indicated by *l*_{m}, stopping the execution when there is no such *f*_{lm}.

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:

MaxIterations | Infinity | maximum number of iterations |

"MaxResults" | Infinity | maximum number of integers in the result |

"SelectionCriterion" | Automatic | test to determine whether an integer should be included in the result |

"ShowProgramLines" | False | if 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 = 2^{4}×3^{7} represents a register state in which the register "2" holds the value 4 and the register "3" the value 7. 2) Each positive fraction *f*_{i} in a program represents an instruction that operates on the integer *n*. The instruction is executed only if *f*_{i} × *n* yields an integer product, otherwise, a negative value will be stored in the register state *n*. For example, the fraction can operate on 2^{4}×3^{7} resulting in 2^{3}×3^{8}, but not on 3^{11} as the final register state would be 2^{-1}×3^{12}.

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

In[1]:= |

Out[1]= |

Decode the answer:

In[2]:= |

Out[2]= |

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

In[3]:= |

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]:= |

Out[64]= |

In[65]:= |

Out[65]= |

Define addition by using the FRACTRAN-1 program:

In[66]:= |

Out[67]= |

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

In[68]:= |

Out[69]= |

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

In[70]:= |

Out[70]= |

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

In[71]:= |

Out[72]= |

This option is most commonly used with "SelectionCriterion":

In[73]:= |

Out[74]= |

For "SelectionCriterion" → *crit*, all integers *n*_{i} of the resulting list for which *crit*[*n*_{i}] is True are picked:

In[75]:= |

Out[76]= |

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

In[77]:= |

Out[77]= |

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

In[78]:= |

Out[78]= |

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]:= |

Out[79]= |

Kilminster's prime number generator:

In[80]:= |

Out[81]= |

Use IntegerLength to get the result:

In[82]:= |

Out[82]= |

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

In[83]:= |

Out[84]= |

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

In[85]:= |

Out[86]= |

Wolfram Language 12.2 (December 2020) or above

- 1.0.0 – 18 January 2021

This work is licensed under a Creative Commons Attribution 4.0 International License