Czy PRIMEGAME Conwaya generuje wszystkie podstawowe moce 2?

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?

reference-request primes

— The Vee
źródło

Artykuł MathWorld , bezpośrednio po cytowanym przez ciebie fragmencie, mówi: „

, ...”. 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^2$

2^{3}

$2^3$

2^{5}

$2^5$

2^{7}

$2^7$

— Chris Pressey

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ε

@ Jɛ ﬀ 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

Tak, PRIMEGAME generuje wtedy i tylko wtedy, gdy $2^k$ $k$ 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