क्या चावल को आलसी बनाना संभव है?

Question

The Genuine Sieve of Erastosthenes पेपर पर, लेखक चलनी के आकार पर पहले एन प्राइम्स की जांच गुणकों को छोड़ने के लिए परिमित आकार के एक चक्र का उपयोग करता है। उदाहरण के लिए, आदेश 2, 3 के गुणकों जाँच से बचने के लिए, आप 5 पर शुरू कर सकते हैं, और बारी-बारी से 2 जोड़ सकते हैं और 4. यह नीचे 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]) 

उसका पहिया पूरी तरह से sieving प्रक्रिया के स्टार्टअप पर उत्पन्न होता है । यह एक ट्रेडऑफ प्रस्तुत करता है, क्योंकि बड़े पहियों को अधिक स्मृति की आवश्यकता होती है। मुझे पहिया पीढ़ी के पीछे अंतर्निहित तंत्र मिल रहा है, हालांकि। इसकी स्पष्ट रूप से दोहराव वाली प्रकृति को देखते हुए, मुझे आश्चर्य है कि "अनंत चक्र" बनाना संभव होगा, जैसे चलनी की तरह, खुद को एक धारा के रूप में प्रस्तुत किया गया? यह धारा, मुझे लगता है, सूचियों के अनुक्रम की सीमा [1], [2], [2, 4], [4, 2, 4, 2, 4, 6, 2, 6]... - और शायद primes के कार्यान्वयन के रूप में कार्य करेगी।

Answer 1

जैसा कि बाकुरी कहते हैं, व्हील अनुक्रम की कोई सीमा नहीं है। "अनंत चक्र" जैसी कोई चीज़ नहीं है, मैं यह दिखाने की कोशिश करूंगा कि क्यों।

हम पहले प्रधानमंत्री संख्या p_1 पता है, ..., p_n, हम केवल संख्या है कि उन्हें करने के लिए कर रहे coprime के बीच अगले वाले खोज करने के लिए की जरूरत है:

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

सेट coprime (p_1 ,. .., p_n) है (p_1 ... p_n) -पीरियोडिक (x इसके अंदर है अगर केवल और यदि x + p_1 ... p_n इसके अंदर है), तो हम इसे एक पहिया कहते हैं।

आप इस कॉप्रिम सेट की सीमा के लिए पूछ रहे हैं, क्योंकि हम अधिक से अधिक प्राइम संख्या p_i लेते हैं। हालांकि, पीआरएन के नीचे कोप्रिम (पी_1, ..., पी_एन) में एकमात्र संख्या है 1. यह साबित करने के लिए, इस प्रकार का एक प्रमुख कारक p_i में से एक होगा।

इसलिए प्राइम की संख्या अनंतता तक जाती है, तो कॉप्रिम (पी_1, ..., पी_एन) 1 और पी_एन के बीच एक विशाल खाली छेद छोड़ देता है। एकमात्र सीमा जिसे आप सोच सकते हैं, इसलिए खाली सेट है: कोई अनंत चक्र नहीं है।