Take the 2-minute tour ×
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.

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?

share|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
2  
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. –  JɛffE 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
add comment

1 Answer

up vote 15 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.) 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|improve this answer
add comment

Your Answer

 
discard

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.