TOPICS
Search

FRACTRAN


Fractran is an algorithm applied to a given list f_1, f_2, ..., f_k of fractions. Given a starting integer N, the FRACTRAN algorithm proceeds by repeatedly multiplying the integer at a given stage by the first element f_i that yields an integer product. The algorithm terminates when there is no such f_i.

The list

 (17)/(91),(78)/(85),(19)/(51),(23)/(38),(29)/(33),(77)/(29),(95)/(23),(77)/(19),1/(17),(11)/(13),(13)/(11),(15)/2,1/7,(55)/1

with starting integer N=2 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: 2^2, 2^3, 2^5, 2^7, ....


See also

Prime Number

Explore with Wolfram|Alpha

References

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."

Referenced on Wolfram|Alpha

FRACTRAN

Cite this as:

Weisstein, Eric W. "FRACTRAN." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/FRACTRAN.html

Subject classifications