¿PRIMEGAME de Conway genera todos los poderes primarios de 2?

La mayoría de los sitios que he visitado leyendo sobre este interesante tema dicen algo similar

"Las únicas potencias de dos (que no sean 2) que ocurren en esta secuencia son aquellas con exponente principal" (MathWorld)

"Después de 2, esta secuencia contiene los siguientes poderes de 2: [...] que son los poderes primarios de 2". (Wikipedia)

Estas formulaciones cuidadosas implicarían que el conjunto de potencias de 2 generadas en la secuencia es un subconjunto de potencias primarias de 2.

Sin embargo, el OEIS parece absolutamente seguro de que los dos conjuntos son iguales: http://oeis.org/A034785

Este resultado también se cita en otros sitios que no considero muy confiables para una redacción exacta, como http://esolangs.org/wiki/Fractran .

Honestamente, todavía no he entendido la mecánica interna de PRIMEGAME para responder mi propia pregunta. Sin embargo, creo que hace una diferencia significativa en el interés de PRIMEGAME. ¿Por qué los sitios como MathWorld no afirman el hecho completo?

reference-request primes El vee
fuente

El artículo de MathWorld , directamente después del pasaje que cita, dice: " , , , , ..." A menos que se sepa que MathWorld es rápido y suelto con elipses, eso sería sugiero fuertemente que la secuencia eventualmente incluya cada potencia principal de dos.

2^{2}

$2^2$

2^{3}

$2^3$

2^{5}

$2^5$

2^{7}

$2^7$

Chris Pressey

Sí, PRIMEGAME genera 2 ^ k si y solo si k es primo. He aquí una explicación por el propio Conway: mathematik.uni-bielefeld.de/~sillke/NEWS/fractran Véase también oeis.org/wiki/Conway's_PRIMEGAME El documento original es bien vale la pena leer si se puede seguir hacia abajo.

Jeffε

@ Jɛ ﬀ E comentario-> respuesta?

Suresh Venkat

nota [ángulo de la teoría de la complejidad] es muy ineficiente. en el artículo de análisis descomponiéndolo en primitivas de subrutina, "Utilizándolos, el autor muestra que el programa Conway es equivalente a un procedimiento bien conocido (aunque altamente ineficiente) para inspeccionar el siguiente número en busca de primalidad. Su análisis en ejecución muestra que inspeccionar la milésima prima (8831) requeriría 468 056 052 pasos atómicos ". Richard K. Guy, Matemáticas. revista 56 (1983), no. 1, 26--33.

vzn

¿PRIMEGAME de Conway genera todos los poderes primarios de 2?

Respuestas: