FRACTRAN is a Turing-complete esoteric programming language invented by the mathematician John Conway. FRACTRAN programs are given as a list of fractions which are applied to a single argument p as follows multiply p by each fraction ƒ in the list in turn until pƒ is an integer; replace p by pƒ and repeat; halt if no member of the list produces an integer when multiplied by p.

PropertyValue
dbpprop:abstract
  • FRACTRAN is a Turing-complete esoteric programming language invented by the mathematician John Conway. FRACTRAN programs are given as a list of fractions which are applied to a single argument p as follows multiply p by each fraction ƒ in the list in turn until pƒ is an integer; replace p by pƒ and repeat; halt if no member of the list produces an integer when multiplied by p. This algorithm can be implemented very simply; for example, in J, a basic FRACTRAN interpretor might be ({~1 i. ~[@@). Conway gave an interesting formula for primes in FRACTRAN <math>\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}. </math> Starting with p=2, this FRACTRAN program generates the following sequence of integers After 2, this sequence contains the following powers of 2 <math>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</math> which are the prime powers of 2.
dbpprop:hasPhotoCollection
dbpprop:reference
rdf:type
rdfs:comment
  • FRACTRAN is a Turing-complete esoteric programming language invented by the mathematician John Conway. FRACTRAN programs are given as a list of fractions which are applied to a single argument p as follows multiply p by each fraction ƒ in the list in turn until pƒ is an integer; replace p by pƒ and repeat; halt if no member of the list produces an integer when multiplied by p.
rdfs:label
  • FRACTRAN
owl:sameAs
skos:subject
foaf:page
is dbpprop:redirect of
is owl:sameAs of