46 lines
2.8 KiB
Plaintext
46 lines
2.8 KiB
Plaintext
'''[[wp:FRACTRAN|FRACTRAN]]''' is a Turing-complete esoteric programming language invented by the mathematician [[wp:John Horton Conway|John Horton Conway]].
|
||
|
||
A FRACTRAN program is an ordered list of positive fractions <math>P = (f_1, f_2, \ldots, f_m)</math>, together with an initial positive integer input <math>n</math>.
|
||
|
||
|
||
The program is run by updating the integer <math>n</math> as follows:
|
||
|
||
* for the first fraction, <math>f_i</math>, in the list for which <math>nf_i</math> is an integer, replace <math>n</math> with <math>nf_i</math> ;
|
||
* repeat this rule until no fraction in the list produces an integer when multiplied by <math>n</math>, then halt.
|
||
|
||
<br>
|
||
Conway gave a program for primes in FRACTRAN:
|
||
|
||
: <math>17/91</math>, <math>78/85</math>, <math>19/51</math>, <math>23/38</math>, <math>29/33</math>, <math>77/29</math>, <math>95/23</math>, <math>77/19</math>, <math>1/17</math>, <math>11/13</math>, <math>13/11</math>, <math>15/14</math>, <math>15/2</math>, <math>55/1</math>
|
||
|
||
Starting with <math>n=2</math>, this FRACTRAN program will change <math>n</math> to <math>15=2\times (15/2)</math>, then <math>825=15\times (55/1)</math>, generating the following sequence of integers:
|
||
|
||
: <math>2</math>, <math>15</math>, <math>825</math>, <math>725</math>, <math>1925</math>, <math>2275</math>, <math>425</math>, <math>390</math>, <math>330</math>, <math>290</math>, <math>770</math>, <math>\ldots</math>
|
||
|
||
After 2, this sequence contains the following powers of 2:
|
||
|
||
:<math>2^2=4</math>, <math>2^3=8</math>, <math>2^5=32</math>, <math>2^7=128</math>, <math>2^{11}=2048</math>, <math>2^{13}=8192</math>, <math>2^{17}=131072</math>, <math>2^{19}=524288</math>, <math>\ldots</math>
|
||
|
||
which are the prime powers of 2.
|
||
|
||
|
||
;Task:
|
||
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).
|
||
|
||
|
||
;Extra credit:
|
||
Use this program to derive the first '''20''' or so prime numbers.
|
||
|
||
|
||
;See also:
|
||
For more on how to program FRACTRAN as a universal programming language, see:
|
||
* J. H. Conway (1987). Fractran: A Simple Universal Programming Language for Arithmetic. In: Open Problems in Communication and Computation, pages 4–26. Springer.
|
||
|
||
* J. H. Conway (2010). "FRACTRAN: A simple universal programming language for arithmetic". In Jeffrey C. Lagarias. The Ultimate Challenge: the 3x+1 problem. American Mathematical Society. pp. 249–264. ISBN 978-0-8218-4940-8. Zbl 1216.68068.
|
||
|
||
* [http://scienceblogs.com/goodmath/2006/10/27/prime-number-pathology-fractra/Prime Number Pathology: Fractran] by Mark C. Chu-Carroll; October 27, 2006.
|
||
<br><br>
|