O PRIMEGAME de Conway gera todos os poderes primos de 2?

17

A maioria dos sites que visitei lendo sobre este tópico interessante afirma algo semelhante

"os únicos poderes de dois (exceto o próprio 2) que ocorrem nessa sequência são aqueles com expoente principal" (MathWorld)

ou

"Após 2, esta sequência contém os seguintes poderes de 2: [...] que são os poderes principais de 2." (Wikipedia)

Essas formulações cuidadosas implicariam que o conjunto de potências de 2 gerado na sequência é um subconjunto de potências primárias de 2.

No entanto, o OEIS parece absolutamente certo de que os dois conjuntos são iguais: http://oeis.org/A034785

Esse resultado também é citado em outros sites que não considero muito confiáveis ​​para termos exatos, como http://esolangs.org/wiki/Fractran .

Honestamente, ainda não compreendi a mecânica interna do PRIMEGAME para responder à minha própria pergunta. No entanto, acho que faz uma diferença significativa no interesse do PRIMEGAME. Por que sites como o MathWorld não afirmam o fato completo?

The Vee
fonte
O artigo do MathWorld , logo após a passagem que você cita, diz: " , 2 3 , 2 5 , 2 7 , ..." A menos que o MathWorld seja conhecido por ser rápido e flexível com elipses, isso seria fortemente sugerido para mim que a sequência eventualmente inclua todo poder primordial de dois. 22232527
precisa
2
Sim, PRIMEGAME gera 2 ^ k se e somente se k for primo. Aqui está uma explicação do próprio Conway: mathematik.uni-bielefeld.de/~sillke/NEWS/fractran Veja também oeis.org/wiki/Conway's_PRIMEGAME Vale a pena ler o artigo original se você puder encontrá -lo.
Jeffε
3
@ Jɛ ff E comentar-> responder?
Suresh Venkat
note [ângulo da teoria da complexidade] é muito ineficiente. no artigo de análise, decompondo-o em primitivas de sub-rotina, "Usando estes, o autor mostra que o programa Conway é equivalente a um procedimento conhecido (embora altamente ineficiente) para inspecionar o próximo número de primalidade. Sua análise em execução mostra que inspecionando o milésimo primo (8831) exigiria 468 056 052 etapas atômicas. " Richard K. Guy, Math. Mag. 56 (1983), n. 1, 26--33.
vzn

Respostas:

26

2kk

Vale a pena ler o artigo original de Conway, se você puder encontrá-lo. Você também pode encontrar uma exposição muito clara na máquina principal de produção de Richard Guy, Conway ( Mathematics Magazine 56 (1): 26–33, 1983), incluindo o maravilhoso desenho abaixo. (Sim, é Conway com os chifres de Alexander, referindo-se a um famoso desenho de Simon Fraser.) O próprio Conway publicou uma prova concisa na lista de discussão divertida em matemática . Há também uma breve explicação no blog da OEIS .

insira a descrição da imagem aqui

Jeffε
fonte
Bela foto!!!
Danny