17

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?

Suresh Venkat
  • 32,071
  • 4
  • 95
  • 271
The Vee
  • 273
  • 1
  • 5
  • 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
  • 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. – Jeffε Dec 14 '12 at 14:59
  • 3
    @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

1 Answers1

26

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

Jeffε
  • 23,129
  • 10
  • 96
  • 163