| This is not an incredible prime-producing machine. It's a fairly ordinary
prime-producing machine. But it is an example of a program in a rather
interesting language. I would not have believed a language would have a syntax
and a semantics which could each be described in one sentence:
A program is an ordered tuple of rational numbers.
Given input x in the form 2**x, repeatedly multiply by the first number
in the tuple that produces an integer, until output is obtained in
the form 2**y.
This describes a complete programming language. Any computable function can
be computed by some program in this language.
Since I am too lazy to look up the articles referenced, I had to determine what
was going on myself. I had a lot of fun discovering the algorithm behind
Conway's program, so I am going to share the process of discovery here.
When I first read the note, I thought some numerical trick was being employed.
Almost immediately, I noted the prime factors that cropped up repeatedly in
the fractions; this told me it was some sort of designed machine, rather than
a "natural" result of numerical properties.
If you go through a few iterations, you should find yourself looking for
certain primes in the denominators; searching for the right number is taking
on some meaning. It occurred to me to rewrite the program in another form:
Fraction | Exponents of Primes in Factor
# value | 2 3 5 7 11 13 17 19 23 29
----------------+------------------------------
0 17/91 | -1 -1 1
1 78/85 | 1 1 -1 1 -1
2 19/51 | -1 -1 1
3 23/38 | -1 -1 1
4 29/33 | -1 -1 1
5 77/29 | 1 1 -1
6 95/23 | 1 1 -1
7 77/19 | 1 1 -1
8 1/17 | -1
9 11/13 | 1 -1
10 13/11 | -1 1
11 15/14 | -1 1 1 -1
12 15/ 2 | -1 1 1
13 55/ 1 | 1 1
Spaces left blank are zero.
The operation of the machine now becomes:
Start with a 10-tuple with input (initially 1) as the first element
of the tuple and all others elements zero. Add the first vector that
does not produce a negative entry. When all elements except the first
are zero, output is the first element.
I highly recommend that readers stop now and try to figure out how the
machine works.
The feel I was getting was that some of the numbers in the tuple were data
being operated on, and some were flags used to inhibit and select various
fractions/tuples/lines of code. The problem is to figure out which lines
follow which and where branches are taken.
I ran the machine through 40 iterations. It had produced 2 as output and was
about to produce 3. At this point, I started analyzing the machine. I noted
that a couple of lines formed a sort of loop that was executed repeatedly at
certain times. For anyone else trying this, I recommend you try to draw a
flowchart. Don't use boxes, it will inhibit things until you know what is
what. Write "input" and draw an arrow and write the number of the fraction
that must be executed first. Then draw an arrow and the number that must be
executed next. If you have done a number of iterations, you may have some idea
of which elements of the tuple are being used as data and which are flags to
indicate which section of the program is being executed. Quite simply, I
decided to use any element that had had a value over 1 as data. This turned
out to be the first four elements. Using names of a, b, c, and d for these
elements, I tried to label on the flowchart what the lines were doing. For
example, at the place marked 12, I wrote:
while (a > 0) a--, b++, c++;
In C this means "While a is greater than zero, subtract one from a and add
one to b and c." If b and c were zero at the start of this line, this line
would be the same as assigning a to b and c, then setting it to zero.
After a couple of hours, I had a complete flowchart. I will not type it in
here, it would be quite a mess. The algorithm I discovered was quite simple,
the program prepares a number and tests it for divisibility by all numbers
less than it. The test for divisibility is accomplished by repeated
subtraction. Subtraction is accomplished by decrementing repeatedly. Conway
has done a very good job of using data efficiently; the number being tested
and the factor being used to test it are both broken down in the process of
testing and then reconstructed. Even so, he was quite fortunate to obtain
fractions with denominators and numerators all less than 100.
I have prepared a C program that follows the algorithm very closely; it follows
the form-feed. The numbers in comments indicate the fractions corresponding to
the C code. Several more programs follow this, each one closer to the way the
algorithm would normally be written. The program should not be too difficult
for anyone who has read this far to follow, but I will point out that the
innermost while-loop has a curious structure. It is used to find the remainder
when one number is divided by another. To accomplish this, it subtract the
divisor from the dividend. Then it "resets itself" and subtracts again. This
repeated subtraction accomplishes the purpose of finding the remainder.
By the way, in the articles cited, is this programming language mentioned,
or is Conway testing to see if anyone is awake?
-- edp
main()
{
int a, b = 0, c = 0, d = 0;
scanf("%d", &a);
do
{
while (a && a--) b++, c++; /* 12 15/2 */
c++; /* 13 55/1 */
do
{
while (b && b--) /* 4 29/23 */
d++; /* 5 77/29 */
/* 10 13/11 */
while (d && d--) /* 0 17/91 */
if (c && c--) a++, b++; /* 1 78/85 */
else if (b && b--) /* 2 19/51 */
{
while (a && a--) /* 3 23/38 */
c++; /* 6 85/23 */
d++; break; /* 7 77/19 */
}
else goto out; /* 8 1/17 */
}
while (1); /* 9 11/13 */
out:
while (d && d--) a--, b++, c++; /* 11 15/14 */
}
while (b || c || d);
printf("%d\n", a);
}
main()
{ int a, b=0, c=0, d=0;
scanf("%d", &a);
do
{ b+=a, c+=a, a=0;
c++;
do
{ d+=b, b=0;
while (d && d--)
if (c && c--) a++, b++;
else if (b)
c+=a, a=0;
else goto out;
}
while (1);
out:
a-=d, b+=d, c+=d, d=0;
}
while (b || c || d);
printf("%d\n", a);
}
main()
{ int a, b=0, c=0, d=0;
scanf("%d", &a);
do
{ b+=a, c+=a, a=0;
c++;
do
{ d+=b, b=0;
if (d <= c)
{ a+=d, b+=d, c-=d, d=0; }
else
{ a+=c, b+=c, d-=c+1, c=0;
if (b)
c+=a, a=0;
else break;
}
}
while (1);
a-=d, b+=d, c+=d, d=0;
}
while (b || c || d);
printf("%d\n", a);
}
main()
{ int a, b, c, d;
scanf("%d", &a);
do
{ b=a, c=a, a=0;
c++;
do
{ a=c;
c=a%b;
a-=c;
if (c)
b--;
else
break;
}
while (b && c);
a+=c;
}
while (b);
printf("%d\n", a);
}
main()
{ int a, b, c, d;
scanf("%d", &a);
do
{ b=a;
a++;
do
{ c=a%b;
if (c)
b--;
else
break;
}
while (b && c);
}
while(b);
printf("%d\n", a);
}
|