Có thể tạo bánh xe uể oải không?

Question

Trên giấy The Genuine Sieve of Erastosthenes, tác giả sử dụng một bánh xe có kích thước hữu hạn để bỏ qua việc kiểm tra bội số của số nguyên tố N đầu tiên trên cấu trúc rây. Ví dụ, để tránh việc kiểm tra bội số của 2, 3, bạn có thể bắt đầu ở 5, và xen kẽ thêm 2 và 4. Đây là wheel 2 dưới đây:

-- 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]) 

bánh xe của cô là hoàn toàn tạo ra trên khởi động của quá trình sàng . Điều này thể hiện sự cân bằng, vì bánh xe lớn hơn cần nhiều bộ nhớ hơn. Tuy nhiên, tôi thấy cơ chế cơ bản đằng sau thế hệ bánh xe thú vị. Với tính chất lặp đi lặp lại rõ ràng của nó, tôi tự hỏi nếu nó sẽ có thể tạo ra một "bánh xe vô hạn" mà, giống như sàng, trình bày chính nó như là một dòng? Luồng này sẽ là, tôi đoán, giới hạn của chuỗi các danh sách [1], [2], [2, 4], [4, 2, 4, 2, 4, 6, 2, 6]... - và có thể hoạt động như một bản thực hiện của chính mình là primes.

Answer 1

Như Bakuriu nói, trình tự bánh xe không có giới hạn. Không có thứ như "bánh xe vô hạn", tôi sẽ cố gắng giải thích tại sao.

Nếu chúng ta biết các số nguyên tố đầu tiên p_1, ..., p_n, chúng tôi chỉ cần phải tìm kiếm những người tiếp theo giữa các số nguyên tố cùng nhau với họ:

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

Tập nguyên tố cùng nhau (p_1 ,. .., p_n) là (p_1 ... p_n) -periodic (x nằm bên trong nó nếu và chỉ khi x + p_1 ... p_n nằm bên trong nó), vì vậy chúng ta gọi nó là bánh xe.

Bạn đang yêu cầu giới hạn tập hợp Coprime này, vì chúng tôi nhận được nhiều số nguyên tố p_i hơn. Tuy nhiên, số duy nhất trong Coprime (p_1, ..., p_n) bên dưới p_n là 1. Để chứng minh điều này, hãy quan sát rằng hệ số nguyên tố của một số như vậy sẽ là một trong p_i.

Vì số lượng số nguyên tố có xu hướng vô cùng, Coprime (p_1, ..., p_n) để lại một lỗ trống lớn giữa 1 và p_n. Giới hạn duy nhất bạn có thể nghĩ ra là do đó bộ trống: không có bánh xe vô hạn.