Tekerleği tempolu üretmek mümkün mü?

Question

The Genuine Sieve of Erastosthenes kağıdında, yazar elek konstrüksiyonundaki ilk N primerlerinin katlarını kontrol etmek için sonlu boyutlu bir tekerlek kullanır.

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

Her tekerlek tamamen eleme sürecinin başlangıcında oluşturulur: Örneğin, 2, 3 katlarını kontrol önlemek için, sen bu aşağıda wheel 2 olan 5 başlayacak ve dönüşümlü 2 ekleyin ve 4. edebilirsiniz . Bu daha büyük tekerlekler daha fazla bellek gerektirdiğinden, bir tradeoff sunar. Yine de, jenerasyonun arkasındaki temel mekanizmayı kendi başına ilginç buluyorum. Açıkça tekrarlanan doğası göz önüne alındığında, elek gibi kendini bir akım olarak sunan bir “sonsuz tekerlek” yaratmanın mümkün olup olmadığını merak ediyorum. Bu akış, sanırım, [1], [2], [2, 4], [4, 2, 4, 2, 4, 6, 2, 6]... listelerinin sırasının sınırı - ve muhtemelen primes'un kendisinin bir uygulaması olarak çalışır.

Answer 1

Bakuriu'nun dediği gibi, tekerlek dizisinin sınırı yoktur. "Sonsuz tekerlek" diye bir şey yoktur, nedenini göstermeye çalışacağım. Biz ilk asal sayılar p_1 biliyorsanız

, ..., P_N, sadece kendilerine asal sayılar arasındaki bir sonraki olanları aramak gerekir:

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

seti asal (p_1 ,. .., p_n) (p_1 ... p_n) -peryodiktir (eğer x + p_1 ... p_n içerideyse x bunun içindedir), biz buna bir tekerlek deriz.

Daha fazla asal sayı aldığımız için bu Coprime kümesinin sınırını soruyorsunuz p_i. Bununla birlikte, p_n altındaki Coprime (p_1, ..., p_n) 'deki tek sayı 1'dir. Bunu kanıtlamak için, böyle bir sayının temel faktörünün p_i'den biri olduğunu gözlemleyin.

Asal sayının sayısı sonsuza kadar arttıkça, Coprime (p_1, ..., p_n) 1 ile p_n arasında büyük bir boş delik bırakır. Düşünebildiğiniz tek sınır bu yüzden boş set: sonsuz bir tekerlek yok.