Talk:Conway's PRIMEGAME

Does the machine halts or not?

Does this algorithm (with this choice of initial integer and list of fractions) terminates or not, since the FRACTRAN algorithm terminates if we cannot obtain an integer by multiplying by any of the fractions from the list? — Daniel Forgues 02:29, 4 January 2012 (UTC)

With that list of fractions, it never terminates; it may get stuck in an infinite loop but it won't terminate (to extend the machine metaphor, the machine would either break down from excessive wear to two of the parts or stop due to a power interruption). The 55 guarantees that if none of the previous numbers of the machine produces an integer, that last one will. — Alonso del Arte 22:29, 4 January 2012 (UTC)

OK, it won't terminate since the last fraction have 1 as denominator. But how do we know for sure that we won't ever end up in a situation where we can only multiply by 55 from some point on... how do we prove that it won't happen? This depends on a very judicious choice for the other thirteen fractions. Better yet would be a proof that if we start with $\scriptstyle 2^{p_{i}},\,i\,\geq \,0,\,p_{0}\,\equiv \,1,\,$ the next power of two will be $\scriptstyle 2^{p_{\{i+1\}}}\,$, where $\scriptstyle p_{i}\,$ is the $\scriptstyle i\,$ th prime. This implies that can't get stuck multiplying by 55 forever from some point onward... — Daniel Forgues 06:20, 5 January 2012 (UTC)

Because 55 has 11 as a prime factor. If the number has neither 3s nor 7s, then the machine will get stuck on the 13/11 to 11/13 cycle.

As for the proof regarding powers of 2 as inputs, I suspect that is in the Guy paper, but JSTOR only lets me see the first page. Alonso del Arte 22:24, 5 January 2012 (UTC)

(Utterly trivial) list of prime factors transformations

The prime factors transformations produced by the above ordered list of fractions are given below, listed in the order of the above list of fractions, where the algorithm stipulates that we have to choose the first one that begets a new integer, the last one being used as a last resort.

$7\cdot 13\left({\tfrac {17}{7\cdot 13}}\right)\to 17\,$

$5\cdot 17\cdot \left({\tfrac {2\cdot 3\cdot 13}{5\cdot 17}}\right)\to 2\cdot 3\cdot 13\,$

$3\cdot 17\cdot \left({\tfrac {19}{3\cdot 17}}\right)\to 19\,$

$2\cdot 19\cdot \left({\tfrac {23}{2\cdot 19}}\right)\to 23\,$

$3\cdot 11\cdot \left({\tfrac {29}{3\cdot 11}}\right)\to 29\,$

$29\cdot \left({\tfrac {7\cdot 11}{29}}\right)\to 7\cdot 11\,$

$23\cdot \left({\tfrac {5\cdot 19}{23}}\right)\to 5\cdot 19\,$

$19\cdot \left({\tfrac {7\cdot 11}{19}}\right)\to 7\cdot 11\,$

$17\cdot \left({\tfrac {1}{17}}\right)\to 1\,$

$13\cdot \left({\tfrac {11}{13}}\right)\to 11\,$

$11\cdot \left({\tfrac {13}{11}}\right)\to 13\,$

$2\cdot \left({\tfrac {3\cdot 5}{2}}\right)\to 3\cdot 5\,$

$7\cdot \left({\tfrac {1}{7}}\right)\to 1\,$

$1\cdot \left({\tfrac {5\cdot 11}{1}}\right)\to 5\cdot 11\,$

I stashed it here, too trivial... — Daniel Forgues 05:47, 5 January 2012 (UTC)

Steps Accuracy

Currently, the article stub lists the following steps for the FRACTRAN program:

At step 0, we have 2, which is multiplied by 15/2 to get...
At step 1, we have 15.
At step 18, we have 68, which is divided by 17 to get...
At step 19, we have 4, giving us the first prime number, 2, as its binary logarithm.
At step 68, we have 136, which is divided by 17 to get...
At step 69, we have 8, giving us the second prime number, 3.
At step 280, we have 544, which is divided by 17 to get...
At step 281, we have 32, giving us the third prime number, 5.
At step 709, we have 2176, which is divided by 17 to get...
At step 710, we have 128, giving us the fourth prime number, 7.

However, based on my Excel program, I am getting the following:

My Steps	Power of 2	Article
0	1	0
19	2	19
69	3	69
280	5	281
707	7	710

It would seem that we are both right. The fractions used in the stub and steps are different than what is shown in the graph. The graph uses the original fractions used in the list and Wikipedia, while the others used the slightly modified, but equivalent, fractions.

Also, looking at the previous step to a prime power, it appears that it always lands on the Ith step (1/17). Is that always true? If so, then that should be added and explained in the article.