Czy możliwe jest leniwe generowanie koła?

Question

Autor artykułu używa koła o skończonym rozmiarze, aby pominąć sprawdzanie wielokrotności pierwszych N liczb pierwszych na konstrukcji sita. Na przykład, w celu uniknięcia kontroli wielokrotności 2, 3, można rozpocząć w 5 i przemian dodać 2 i 4. Jest to poniżej wheel 2:

-- wheel 0 = ([2],[1]) 
-- wheel 1 = ([3,2],[2]) 
-- wheel 2 = ([5,3,2],[2,4]) -- "start at 5, add 2, 4, 2, 4..." 
-- wheel 3 = ([7,5,3,2],[4,2,4,2,4,6,2,6]) 

Jej koło jest całkowicie generowane na starcie procesu przesiewania . To stanowi kompromis, ponieważ większe koła wymagają więcej pamięci. Uważam jednak, że mechanizm leżący u podstaw tego koła jest interesujący sam w sobie. Biorąc pod uwagę jego wyraźnie powtarzalny charakter, zastanawiam się, czy byłoby możliwe stworzenie "nieskończonego koła", które, podobnie jak sito, prezentowało się jako strumień? Ten strumień byłby, jak sądzę, granicą sekwencji list [1], [2], [2, 4], [4, 2, 4, 2, 4, 6, 2, 6]... - i prawdopodobnie działa jako implementacja samego siebie.

Answer 1

Jak mówi Bakuriu, sekwencja kół nie ma limitu. Nie ma czegoś takiego jak "nieskończone koło", postaram się wykazać, dlaczego.

Jeśli znamy pierwsze cyfry prime P_1, ..., P_N, tylko trzeba szukać kolejnych te spośród numerów, które są względnie pierwsze do nich:

isCoprime :: [Int] -> Int -> Bool 
isCoprime ps x = all (\p -> x `mod` p /= 0) ps 

Zestaw względnie pierwsze (P_1 ,. .., p_n) to (p_1 ... p_n) -periodyczne (x jest w nim wtedy i tylko wtedy, gdy x + p_1 ... p_n jest w nim), więc nazywamy to kółkiem.

Pytasz o limit tego zestawu Coprime, ponieważ przyjmujemy coraz więcej liczb pierwszych p_i. Jednak jedyną liczbą w Coprime (p_1, ..., p_n) poniżej p_n jest 1. Aby to udowodnić, należy zauważyć, że czynnikiem decydującym o takiej liczbie byłby jeden z p_i.

Tak jak liczba liczb pierwszych ma nieskończoność, Coprime (p_1, ..., p_n) pozostawia ogromną pustą dziurę pomiędzy 1 a p_n. Jedynym ograniczeniem, jakie można sobie wyobrazić, jest zatem pusty zestaw: nie ma nieskończonego koła.