Czy PRIMEGAME Conwaya generuje wszystkie podstawowe moce 2?

17

Większość stron, które odwiedziłem czytając ten interesujący temat, podaje coś podobnego

„jedynymi potęgami dwóch (innych niż 2), które występują w tej sekwencji, są te z głównym wykładnikiem potęgi” (MathWorld)

lub

„Po 2 sekwencja ta zawiera następujące potęgi 2: [...], które są podstawowymi potęgami 2”. (Wikipedia)

Te staranne sformułowania sugerowałyby, że zbiór potęg 2 generowanych w sekwencji jest podzbiorem potęg pierwszych 2.

Jednak OEIS wydaje się absolutnie pewne, że oba zestawy są równe: http://oeis.org/A034785

Ten wynik jest również cytowany na innych stronach, które nie uważam za bardzo wiarygodne pod względem dokładnego sformułowania, takich jak http://esolangs.org/wiki/Fractran .

Szczerze mówiąc, nie zrozumiałem jeszcze wewnętrznej mechaniki PRIMEGAME, aby odpowiedzieć na moje własne pytanie. Myślę jednak, że ma to znaczący wpływ na ciekawość PRIMEGAME. Dlaczego strony takie jak MathWorld nie przedstawiają pełnego faktu?

The Vee
źródło
Artykuł MathWorld , bezpośrednio po cytowanym przez ciebie fragmencie, mówi: „ , 2 3 , 2 5 , 2 7 , ...”. O ile nie wiadomo, że MathWorld jest szybki i luźny z elipsami, to zdecydowanie by mi to sugerowało że sekwencja ostatecznie obejmuje każdą pierwszą potęgę dwóch. 2)2)2)3)2)52)7
Chris Pressey
2
Tak, PRIMEGAME wyprowadza 2 ^ k wtedy i tylko wtedy, gdy k jest liczbą pierwszą. Oto jedno wyjaśnienie samego Conwaya: mathematik.uni-bielefeld.de/~sillke/NEWS/fractran Zobacz także oeis.org/wiki/Conway's_PRIMEGAME Oryginalny artykuł warto przeczytać, jeśli można go wyśledzić.
Jeffε
3
@ Jɛ ff E komentarz-> odpowiedź?
Suresh Venkat,
zauważ [kąt teorii złożoności] jest bardzo nieefektywny. w artykule analitycznym rozkładającym go na prymitywy podprogramu: „Korzystając z nich, autor pokazuje, że program Conwaya jest równoważny dobrze znanej (choć wysoce nieefektywnej) procedurze sprawdzania następnej liczby pod kątem pierwszeństwa. Jego bieżąca analiza pokazuje, że sprawdzanie tysięcznej liczby pierwszej (8831) wymagałoby 468 056 052 kroków atomowych. ” Richard K. Guy, Math. Mag. 56 (1983), no. 1, 26--33.
vzn 14.12.12

Odpowiedzi:

26

Tak, PRIMEGAME generuje wtedy i tylko wtedy, gdy k2)kk jest liczbą pierwszą.

Oryginalny papier Conwaya jest wart przeczytania, jeśli możesz go wyśledzić. Bardzo wyraźną ekspozycję można także znaleźć w artykule Richarda Guya, głównej maszynie produkcyjnej Conwaya ( Mathematics Magazine 56 (1): 26–33, 1983), w tym wspaniałą kreskówkę poniżej. (Tak, to Conway z rogami Aleksandra, nawiązujący do słynnego rysunku Simona Frasera). Sam Conway umieścił zwięzły dowód na liście matematycznej . Istnieje również krótkie wyjaśnienie na blogu OEIS .

wprowadź opis zdjęcia tutaj

Jeffε
źródło
Świetne zdjęcie!!!
Danny