<p>Yes, PRIMEGAME outputs $2^k$ if and only if $k$ is prime.</p>

<p>Conway's original paper is well worth reading if you can track it down.  You can also find a very clear exposition in Richard Guy's paper <a href="http://www.jstor.org/stable/2690263" rel="noreferrer">Conway's prime producing machine</a> (<em>Mathematics Magazine</em> 56(1):26–33, 1983), including the wonderful cartoon below. (Yes, that's Conway with the Alexander horns, referring to a famous drawing by Simon Fraser.)  Conway himself posted <a href="http://www.mathematik.uni-bielefeld.de/~sillke/NEWS/fractran" rel="noreferrer">a concise proof on the math-fun mailing list</a>.  There's also <a href="http://oeis.org/wiki/Conway&#39;s_PRIMEGAME" rel="noreferrer">a brief explanation at the OEIS blog</a>.</p>

<p><img src="https://i.sstatic.net/6ZPkF.jpg" alt="enter image description here"></p>

CC BY-SA 3.0
2015-05-29T11:01:40.367Z
Great picture!!!
Danny
CC BY-SA 3.0
2012-12-14T17:51:29.253Z
2015-05-27T21:02:45.690Z
2015-05-27T21:02:45.690Z
Jeffε
<p>Most sites I have visited reading on this interesting topic state something along the lines</p>

<blockquote>
  <p>"the only powers of two (other than 2 itself) that occur in this sequence are those with prime exponent" (MathWorld)</p>
</blockquote>

<p>or</p>

<blockquote>
  <p>"After 2, this sequence contains the following powers of 2: [...] which are the prime powers of 2." (Wikipedia)</p>
</blockquote>

<p>These careful formulations would imply that the set of powers of 2 generated in the sequence is a subset of prime powers of 2.</p>

<p>However, the OEIS seems absolutely certain that the two sets are equal: <a href="http://oeis.org/A034785">http://oeis.org/A034785</a></p>

<p>This result is also cited on other sites I do not consider very reliable for exact wording, like
<a href="http://esolangs.org/wiki/Fractran">http://esolangs.org/wiki/Fractran</a>.</p>

<p>Honestly, I have not understood the internal mechanics of PRIMEGAME enough to answer my own question yet. However, I think it makes a significant difference in the interestingness of PRIMEGAME. Why would sites like MathWorld not state the full fact?</p>

CC BY-SA 3.0
2012-12-14T12:41:51.057Z
[The MathWorld article](http://mathworld.wolfram.com/FRACTRAN.html), directly after the passage you quote, says: "$2^2$, $2^3$, $2^5$, $2^7$, ..."  Unless MathWorld is known to be fast-and-loose with ellipses, that would strongly suggest to me that the sequence eventually includes every prime power of two.
Chris Pressey
CC BY-SA 3.0
2012-12-14T14:59:54.760Z
Yes, PRIMEGAME outputs 2^k if and only if k is prime.  Here's one explanation by Conway himself: http://www.mathematik.uni-bielefeld.de/~sillke/NEWS/fractran  See also  https://oeis.org/wiki/Conway's_PRIMEGAME  The original paper is well worth reading if you can track it down.
Jeffε
CC BY-SA 3.0
2012-12-14T16:21:41.250Z
@JɛﬀE comment->answer ?
Suresh Venkat
CC BY-SA 3.0
2012-12-14T20:09:07.183Z
note [complexity-theory angle] its very inefficient. in analysis article decomposing it into subroutine primitives, "Using these, the author shows that the Conway program is equivalent to a well-known (although highly inefficient) procedure for inspecting the next number for primality. His running analysis shows that inspecting the thousandth prime (8831) would require 468 056 052 atomic steps." Richard K. Guy, Math. Mag. 56 (1983), no. 1, 26--33.
vzn
<reference-request><primes>
Does Conway's PRIMEGAME generate all prime powers of 2?
The Vee
# Does Conway's PRIMEGAME generate all prime powers of 2?

(Asked by: username_0 on 2012-12-14)

Most sites I have visited reading on this interesting topic state something along the lines

> "the only powers of two (other than 2 itself) that occur in this sequence are those with prime exponent" (MathWorld)

or

> "After 2, this sequence contains the following powers of 2: [...] which are the prime powers of 2." (Wikipedia)

These careful formulations would imply that the set of powers of 2 generated in the sequence is a subset of prime powers of 2.

However, the OEIS seems absolutely certain that the two sets are equal: <http://oeis.org/A034785>

This result is also cited on other sites I do not consider very reliable for exact wording, like
<http://esolangs.org/wiki/Fractran>.

Honestly, I have not understood the internal mechanics of PRIMEGAME enough to answer my own question yet. However, I think it makes a significant difference in the interestingness of PRIMEGAME. Why would sites like MathWorld not state the full fact?

**Tags:** reference-request, primes

> **Comments:**
> **username_1**: [The MathWorld article](http://mathworld.wolfram.com/FRACTRAN.html), directly after the passage you quote, says: "$2^2$, $2^3$, $2^5$, $2^7$, ..."  Unless MathWorld is known to be fast-and-loose with ellipses, that would strongly suggest to me that the sequence eventually includes every prime power of two.  
> **username_2**: Yes, PRIMEGAME outputs 2^k if and only if k is prime.  Here's one explanation by Conway himself: http://www.mathematik.uni-bielefeld.de/~sillke/NEWS/fractran  See also  https://oeis.org/wiki/Conway's_PRIMEGAME  The original paper is well worth reading if you can track it down.  
> **username_3**: @JɛﬀE comment->answer ?  
> **username_4**: note [complexity-theory angle] its very inefficient. in analysis article decomposing it into subroutine primitives, "Using these, the author shows that the Conway program is equivalent to a well-known (although highly inefficient) procedure for inspecting the next number for primality. His running analysis shows that inspecting the thousandth prime (8831) would require 468 056 052 atomic steps." Richard K. Guy, Math. Mag. 56 (1983), no. 1, 26--33.  

---

## 1 answers

### Answer by username_2 on 2012-12-14. Score: 26 | Accepted answer

Yes, PRIMEGAME outputs $2^k$ if and only if $k$ is prime.

Conway's original paper is well worth reading if you can track it down. You can also find a very clear exposition in Richard Guy's paper [Conway's prime producing machine](http://www.jstor.org/stable/2690263) (*Mathematics Magazine* 56(1):26–33, 1983), including the wonderful cartoon below. (Yes, that's Conway with the Alexander horns, referring to a famous drawing by Simon Fraser.) Conway himself posted [a concise proof on the math-fun mailing list](http://www.mathematik.uni-bielefeld.de/~sillke/NEWS/fractran). There's also [a brief explanation at the OEIS blog](http://oeis.org/wiki/Conway's_PRIMEGAME).

![enter image description here](https://i.sstatic.net/6ZPkF.jpg)

> **Comments:**
> **username_5**: Great picture!!!  

---

