Fractran is an algorithm applied to a given list , ,
..., of fractions.
Given a starting integer, the FRACTRAN algorithm proceeds by repeatedly multiplying
the integer at a given stage by the first element that yields an integer product.
The algorithm terminates when there is no such .
The list
with starting integer
generates a sequence 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, ... (OEIS
A007542). Conway (1987) showed that this sequence
has an amazing connection with prime numbers, and in fact is a generator for the
primes. In particular, the only powers of two (other than 2 itself) that occur in
this sequence are those with prime exponent: , , ,
, ....
Conway, J. H. "Unpredictable Iterations." In Proceedings of the 1972 Number Theory Conference Held at the University of
Colorado, Boulder, Colo., Aug. 14-18, 1972. Boulder, CO: University of Colorado,
pp. 49-52, 1972.Conway, J. H. "Fractran: A Simple Universal
Programming Language for Arithmetic." Ch. 2 in Open
Problems in Communication and Computation (Ed. T. M. Cover and
B. Gopinath). New York: Springer-Verlag, pp. 4-26, 1987.Sloane,
N. J. A. Sequence A007542/M2084
in "The On-Line Encyclopedia of Integer Sequences."
, 
,
..., 
of fractions.
Given a starting integer 
, the FRACTRAN algorithm proceeds by repeatedly multiplying
the integer at a given stage by the first element 
that yields an integer product.
The algorithm terminates when there is no such 
.
generates a sequence 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, ... (OEIS
A007542). Conway (1987) showed that this sequence
has an amazing connection with prime numbers, and in fact is a generator for the
primes. In particular, the only powers of two (other than 2 itself) that occur in
this sequence are those with prime exponent: 
, 
, 
,
, ....
