Nonplussed! (43 page)

are fractions. The Fractran machine works by inputting a positive integer
N
into the lowest numbered line and replacing it by
p
_i
/
q
_i
×
N
for the least
i
for which this is an integer, and then branch to line
n
_i
; if no such integer is possible, the process terminates.

For example,
will multiply the input by
and change the program flow to line 15 if that product is an integer, otherwise it will multiply the input by
and change the program flow to line 20 if that product is an integer, and failing both of these it will stop.

We are interested in fraction lists. In general, the fraction list

has the Fractran equivalent of the
r
lined program:

which is an example of what Conway calls a Fractran-
r
program.

More compactly, this particular example can be written as the Fractran-1 program:

In asking whether our multiplication program can be written as a fraction list, we are asking whether this Fractran-3 program can be written as a Fractran-1 program. In fact, in his article Con-way demonstrates a method which allows an arbitrary Fractran-
r
program to be simulated by a Fractran-1 program, and therefore a fraction list; it uses the unique factorization property of the primes:

(1) Clear the program of all loops.

(2) Label the nodes of the diagram with distinct primes
P,Q, R,…
larger than any primes appearing in the numerators or denominators of its fractions: these will form the new line numbers.

(3) Translate, in order, a line at a time by using the scheme

(4) Populate the fraction list in the correct order.

In the case of the multiplication he redesigned
figure 14.5
to
figure 14.6
.

Figure 14.6.
The multiplication loops modified.

Now rewrite the line numbers accordingly to get the Fractran program:

and use the algorithm to generate the fraction list

Notice the order of the fractions, with the second entries on the two lines fitting into their proper places.

The reader can check that starting with
r
₂
=
a
,
r
₃
=
b
,
r
₅
= 0,
r
₇
=
c
,
r
₁₁
= 1 and hence
N
= 2
^a
×
3
^b
×
7
^c
×11 results in
r
₂
=
a + bc
,
r
₃
=
b
,
r
₅
= 0,
r
₇
= 0,
r
¹¹
= 1 and hence
N
= 2
^a+bc
× 3
^b
× 11.

We can interpret these prime node labels as states of the Frac-tran machine. Doing so and disassembling the fraction as

enables us to interpret each fraction in the following way: