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)


"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?

  • $\begingroup$ The MathWorld article, 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. $\endgroup$ Dec 14, 2012 at 12:41
  • 2
    $\begingroup$ Yes, PRIMEGAME outputs 2^k if and only if k is prime. Here's one explanation by Conway himself: mathematik.uni-bielefeld.de/~sillke/NEWS/fractran See also oeis.org/wiki/Conway's_PRIMEGAME The original paper is well worth reading if you can track it down. $\endgroup$
    – Jeffε
    Dec 14, 2012 at 14:59
  • 3
    $\begingroup$ @JɛffE comment->answer ? $\endgroup$ Dec 14, 2012 at 16:21
  • $\begingroup$ 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. $\endgroup$
    – vzn
    Dec 14, 2012 at 20:09

1 Answer 1


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 (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. There's also a brief explanation at the OEIS blog.

enter image description here

  • $\begingroup$ Great picture!!! $\endgroup$
    – Danny
    May 29, 2015 at 11:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.