Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:

This result is also cited on other sites I do not consider very reliable for exact wording, like

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?

share|cite|improve this question
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. – Chris Pressey Dec 14 '12 at 12:41
Yes, PRIMEGAME outputs 2^k if and only if k is prime. Here's one explanation by Conway himself: See also's_PRIMEGAME The original paper is well worth reading if you can track it down. – Jeffε Dec 14 '12 at 14:59
@JɛffE comment->answer ? – Suresh Venkat Dec 14 '12 at 16:21
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 Dec 14 '12 at 20:09
up vote 24 down vote accepted

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

share|cite|improve this answer
Great picture!!! – Danny May 29 '15 at 11:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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