FRACTRAN

FRACTRAN is a Turing-complete esoteric programming language invented by the mathematician John Conway. A FRACTRAN program is an ordered list of positive fractions together with an initial positive integer input n. The program is run by updating the integer n as follows: #for the first fraction f in the list for which nf is an integer, replace n by nf #repeat this rule until no fraction in the list produces an integer when multiplied by n, then halt. gives the following FRACTRAN program, called PRIMEGAME, which finds successive prime numbers: \left( \frac{17}{91}, \frac{78}{85}, \frac{19}{51}, \frac{23}{38}, \frac{29}{33}, \frac{77}{29}, \frac{95}{23}, \frac{77}{19}, \frac{1}{17}, \frac{11}{13}, \frac{13}{11}, \frac{15}{2}, \frac{1}{7}, \frac{55}{1} \right) Starting with n=2, this FRACTRAN program generates the following sequence of integers: * 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, ... , i.e. the sequence of PRIMEGAME numbers After 2, this sequence contains the following powers of 2: 2^2=4,\, 2^3=8,\, 2^5=32,\, 2^7=128,\, 2^{11}=2048,\, 2^{13}=8192,\, 2^{17}=131072,\, 2^{19}=524288,\, \dots The exponent part of these powers of two are primes, 2, 3, 5, etc.

FRACTRAN is a Turing-complete esoteric programming language invented by the mathematician John Conway. A FRACTRAN program is an ordered list of positive fractions together with an initial positive integer input n. The program is run by updating the integer n as follows: for the first fraction f in the list for which nf is an integer, replace n by nf repeat this rule until no fraction in the list produces an integer when multiplied by n, then halt. gives the following FRACTRAN program, called PRIMEGAME, which finds successive prime numbers: \left( \frac{17}{91}, \frac{78}{85}, \frac{19}{51}, \frac{23}{38}, \frac{29}{33}, \frac{77}{29}, \frac{95}{23}, \frac{77}{19}, \frac{1}{17}, \frac{11}{13}, \frac{13}{11}, \frac{15}{2}, \frac{1}{7}, \frac{55}{1} \right) Starting with n=2, this FRACTRAN program generates the following sequence of integers: 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, ... , i.e. the sequence of PRIMEGAME numbers After 2, this sequence contains the following powers of 2: 2^2=4,\, 2^3=8,\, 2^5=32,\, 2^7=128,\, 2^{11}=2048,\, 2^{13}=8192,\, 2^{17}=131072,\, 2^{19}=524288,\, \dots The exponent part of these powers of two are primes, 2, 3, 5, etc. 60 = 2^2 \times 3^1 \times 5^1 represents a register state in which one variable (which we will call v_2 ) holds the value 2 and two other variables ( v_3 and v_5 ) hold the value 1. All other variables hold the value 0. A FRACTRAN program is an ordered list of positive fractions. Each fraction represents an instruction that tests one or more variables, represented by the prime factors of its denominator. For example: f_1 = \frac{21}{20} = \frac{3 \times 7}{2^2 \times 5^1} tests v_2 and v_5 . If v_2 \ge 2 and v_5 \ge 1 , then it subtracts 2 from v_2 and 1 from v_5 and adds 1 to v_3 and 1 to v_7 . For example: 60 \cdot f_1 = 2^2 \times 3^1 \times 5^1 \cdot \frac{3 \times 7}{2^2 \times 5^1} = 3^2 \times 7^1 Since the FRACTRAN program is just a list of fractions, these test-decrement-increment instructions are the only allowed instructions in the FRACTRAN language. In addition the following restrictions apply: Each time an instruction is executed, the variables that are tested are also decremented. The same variable cannot be both decremented and incremented in a single instruction (otherwise the fraction representing that instruction would not be in its lowest terms). Therefore each FRACTRAN instruction consumes variables as it tests them. It is not possible for a FRACTRAN instruction to directly test if a variable is 0 (However, an indirect test can be implemented by creating a default instruction that is placed after other instructions that test a particular variable.). \left( \frac{3}{2} \right) This program can be represented as a (very simple) algorithm as follows: Given an initial input of the form 2^a 3^b , this program will compute the sequence 2^{a-1} 3^{b+1} , 2^{a-2} 3^{b+2} , etc., until eventually, after a steps, no factors of 2 remain and the product with \frac{3}{2} no longer yields an integer; the program then stops with a final output of 3^{a + b} . It therefore adds two integers together. \left( \frac{455}{33}, \frac{11}{13}, \frac{1}{11}, \frac{3}{7}, \frac{11}{2}, \frac{1}{3} \right) With input 2 a 3 b this program produces output 5 ab . \left( \frac{91}{66}, \frac{11}{13}, \frac{1}{33}, \frac{85}{11}, \frac{57}{119}, \frac{17}{19}, \frac{11}{17}, \frac{1}{3} \right) and input 2 n 3 d 11 produces output 5 q 7 r where n = qd + r and 0 ≤ r \left( \frac{17}{91}, \frac{78}{85}, \frac{19}{51}, \frac{23}{38}, \frac{29}{33}, \frac{77}{29}, \frac{95}{23}, \frac{77}{19}, \frac{1}{17}, \frac{11}{13}, \frac{13}{11}, \frac{15}{14}, \frac{15}{2}, \frac{55}{1} \right) This variant is a little faster: reaching 2, 3, 5, 7... takes it 19, 69, 280, 707... steps . A single iteration of this program, checking a particular number N for primeness, takes the following number of steps: N - 1 + (6N+2)(N-b) + 2 \sum\limits^{N-1}_{d=b} \left\lfloor \frac{N}{d} \right\rfloor, where b is the largest integer divisor of N and \lfloor x \rfloor is the floor function. In 1999, Devin Kilminster demonstrated a shorter, ten-instruction program: \left( \frac{7}{3}, \frac{99}{98}, \frac{13}{49}, \frac{39}{35}, \frac{36}{91}, \frac{10}{143}, \frac{49}{13}, \frac{7}{11}, \frac{1}{2}, \frac{91}{1} \right). For the initial input n = 10 successive primes are generated by subsequent powers of 10. \left( \frac{3 \cdot 11}{2^2 \cdot 5} , \frac{5}{11}, \frac{13}{2 \cdot 5}, \frac{1}{5}, \frac{2}{3}, \frac{2 \cdot 5}{7}, \frac{7}{2} \right) calculates the Hamming weight H(a) of the binary expansion of a i.e. the number of 1s in the binary expansion of a. Given input 2 a , its output is 13 H(a) . The program can be analysed as follows: ===PIGAME=== In Conways original article from 1987, he also gave PIGAME (Theorem 2, page 5), a FRACTRAN program consisting of 40 fractions, PIGAME = \left(\frac{365}{46}, \frac{29}{161}, \frac{79}{575}, \frac{679}{451}, \frac{3159}{413}, \frac{83}{407}, \frac{473}{371}, \frac{638}{355}, \frac{434}{335}, \frac{89}{235}, \frac{17}{209}, \frac{79}{122}, \frac{31}{183}, \frac{41}{115}, \frac{517}{89}, \frac{111}{83}, \frac{305}{79}, \right. \qquad\left. \frac{23}{73}, \frac{73}{71}, \frac{61}{67}, \frac{37}{61}, \frac{19}{59}, \frac{89}{57}, \frac{41}{53}, \frac{833}{47}, \frac{53}{43}, \frac{86}{41}, \frac{13}{38}, \frac{23}{37}, \frac{67}{31}, \frac{71}{29}, \frac{83}{19}, \frac{475}{17}, \frac{59}{13}, \frac{41}{291}, \frac{1}{7}, \frac{1}{11}, \frac{1}{1024}, \frac{1}{97}, \frac{89}{1} \right)~, which can compute any decimal digit of the constant : To get , the -th decimal digit of , where by convention the initial digit 3 corresponds to , the PIGAME must be played starting with 2^n\cdot89 (not 2^n as incorrectly written in the paper). Then, the first power of two appearing in the trajectory will be 2^{\pi(n)} . Indeed, when started with 89 (i.e., ), the first power of two to appear, at the 775-th iteration, is 8 = 2^3, corresponding to the initial digit 3 of . Prime Number Pathology FRACTRAN - (Esolang wiki) Ruby implementation and example programs Project Euler Problem 308 "Building Fizzbuzz in Fractran from the Bottom Up" Chris Lomont, "A Universal FRACTRAN Interpreter in FRACTRAN"

Text derived from https://en.wikipedia.org/w/index.php?oldid=1374406127 under CC BY-SA 4.0; modifications have been made.