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$ given an integer Product. The algorithm terminates when there is no such $f_i$.

The list

$${17\over 91}, {78\over 85}, {19\over 51}, {23\over 38}, {29\... ...1\over 13}, {13\over 11}, {15\over 2}, {1\over 7}, {55\over 1}$$

with starting integer $N=2$ generates a sequence 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, ... (Sloane's A007542). Conway (1987) showed that the only other powers of 2 which occur are those with Prime exponent: $2^2$, $2^3$, $2^5$, $2^7$, ....

References

Conway, J. H. ``Unpredictable Iterations.'' In Proc. Number Theory Conf., Boulder, CO, 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 ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html and Sloane, N. J. A. and Plouffe, S. The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.