क्या एनएच प्राइम के अनुमानित मूल्य को खोजने का कोई तरीका है?

Question

क्या कोई ऐसा फ़ंक्शन है जो n वें प्राइम का अनुमानित मान वापस करेगा? मुझे लगता है कि यह लगभग अनुमानित प्राइम गिनती समारोह की तरह कुछ होगा। उदाहरण के लिए, अगर मैंने यह फ़ंक्शन 25 दिया है तो यह लगभग 100 नंबर लौटाएगा, या अगर मैंने यह फ़ंक्शन 1000 दिया है तो यह लगभग 8000 की संख्या लौटाएगा। मुझे कोई परवाह नहीं है कि लौटाया गया नंबर प्राइम है या नहीं, लेकिन मैं चाहता हूं यह तेज़ होने के लिए (ताकि कोई पहली n रूढ़ अंक पैदा n वें वापस जाने के लिए।)

मुझे यह पसंद है, ताकि मैं पहली बार n प्रधानमंत्री एक छलनी का उपयोग कर संख्या उत्पन्न कर सकते हैं होगा (Eratosthenes या Atkin)। इसलिए, n वें अनुमानित रूप से वास्तविक n वें प्राइम के मूल्य को कम से कम अनुमानित नहीं करेगा।

(अद्यतन: n वें अभाज्य संख्या की ऊपरी सीमा को खोजने का एक अच्छा तरीका के लिए my answer देखें।)

Answer 1

कसकर सीमा:

static const unsigned short primes_small[] = {0,2,3,5,7,11}; 

static unsigned long nth_prime_upper(unsigned long n) { 
    double fn = (double) n; 
    double flogn, flog2n, upper; 
    if (n < 6) return primes_small[n]; 
    flogn = log(n); 
    flog2n = log(flogn); 

    if  (n >= 688383) /* Dusart 2010 page 2 */ 
    upper = fn * (flogn + flog2n - 1.0 + ((flog2n-2.00)/flogn)); 
    else if (n >= 178974) /* Dusart 2010 page 7 */ 
    upper = fn * (flogn + flog2n - 1.0 + ((flog2n-1.95)/flogn)); 
    else if (n >= 39017) /* Dusart 1999 page 14 */ 
    upper = fn * (flogn + flog2n - 0.9484); 
    else     /* Modified from Robin 1983 for 6-39016 _only_ */ 
    upper = fn * (flogn + 0.6000 * flog2n); 

    if (upper >= (double) ULONG_MAX) { 
    /* Adjust this as needed for your type and exception method */ 
    if (n <= 425656284035217743UL) return 18446744073709551557UL; 
    fprintf(stderr, "nth_prime_upper overflow\n"; exit(-1); 
    } 

    return (unsigned long) ceil(upper); 
} 

ये कभी वास्तविक nth_prime से कम नहीं होना चाहिए, किसी भी 64-बिट इनपुट के लिए काम करना चाहिए, और या परिमाण के एक आदेश से सूत्र की तुलना में अधिक करीब हो रॉबिन पहले दिया गया था (या विंबब्लिक की जटिल सीमा-सीमित सूत्र)। मेरे उपयोग के लिए मेरे पास थोड़ा बड़ा प्राइम टेबल है, इसलिए अंतिम अनुमान को थोड़ा और मजबूत कर सकता है। तकनीकी रूप से सूत्रों से हम छत() के बजाय फर्श() का उपयोग कर सकते हैं लेकिन मुझे परिशुद्धता की चिंता है।

संपादित करें: इसे थोड़ा सुधारने के लिए एक और विकल्प अच्छी प्रधान गणना सीमाओं (उदाहरण के लिए एक्सलर 2014) को लागू करना और उन पर बाइनरी खोज करना है। इस विधि के लिए मेरा कोड उपरोक्त से ~ 10x लंबा (अभी भी मिलीसेकंड के नीचे चल रहा है) लेता है, लेकिन परिमाण के क्रम से त्रुटि प्रतिशत को कम कर सकता है।

आप वें प्रधानमंत्री के लिए एक अनुमान चाहते हैं, आप कर सकते हैं:

• सिपोला 1902 (Dusart 1999 पेज 12 या this paper देख मैं तीन शर्तों (एम = 2) के साथ साथ करने के लिए एक तीसरे क्रम सुधार कारक हैं। उपयोगी हो, लेकिन अधिक शर्तों के साथ यह बहुत अधिक हो जाता है। विकिपीडिया लिंक में दिखाया गया सूत्र यह सूत्र है (एम = 2 के साथ)। दो-टर्म उलटा ली या विपरीत रिमेंन आर का उपयोग बेहतर परिणाम देगा।
• गणना करें Dusart 2010 ऊपरी और निचली सीमाएं और परिणाम औसत। बहुत बुरा नहीं है, हालांकि मुझे लगता है कि भारित औसत का उपयोग करने पर संदेह बेहतर होगा क्योंकि सीमाएं समान रूप से तंग नहीं हैं।
• ली^{- 1} (एन) चूंकि ली (एन) प्रमुख गणना के लिए एक सभ्य अनुमान है, उलटा एक सभ्य nth_prime अनुमान है। यह, और बाकी सभी, समारोह पर एक बाइनरी खोज के रूप में काफी जल्दी किया जा सकता है।
• ली^{- 1} (एन) + ली^{- 1} (एसकर्ट (एन))/4 करीब, क्योंकि यह आर (एन)
• आर^{- 1} के विपरीत हो रहा है रिमेंन आर फ़ंक्शन निकटतम औसत अनुमान है जो मुझे पता है कि यह उचित है।

आखिरकार, यदि आपके पास एलएमओ कार्यान्वयन में से एक बहुत तेज़ प्राइम गिनती विधि है (अब तीन खुले स्रोत कार्यान्वयन हैं), तो आप एक तेज सटीक nth_prime विधि लिख सकते हैं। 10^10 वें प्राइम की कंप्यूटिंग कुछ मिलीसेकंड में की जा सकती है, और कुछ सेकंड में 10^13 वें (आधुनिक फास्ट मशीन पर)। अनुमान लगभग सभी आकारों पर काम करते हैं और बहुत बड़ी संख्या के लिए काम करते हैं, लेकिन सभी के पास "बड़े" साधनों का एक अलग विचार है।

Answer 2

Prime number theorem एक सीमा मूल्य से नीचे अभाज्य संख्या की एक संख्या देता है, तो इसे देने के लिए इस्तेमाल किया जा सकता एनएच प्राइम के लिए अनुमानित मूल्य।

Answer 3

किसी न किसी अनुमान के रूप में, आप एन * एलएन (एन) का उपयोग एनएच प्राइम नंबर के अनुमान के रूप में कर सकते हैं। एक और अधिक जटिल, लेकिन अधिक सटीक विधि है, जिसका विवरण आप विकिपीडिया here पर पा सकते हैं।

Answer 4

एक चाकू के साथ संभवतः एक कुशल कार्यान्वयन संभव नहीं है। सोचें कि क्या होगा यदि आप पहले 10.000 प्राइम नंबर चाहते हैं। आपको शायद बड़ी संख्या में संख्याओं पर चलनी पड़ेगी।

this question और my answer में आपका स्वयं का इम्प्लांटेशन अनुमोदन को जानने के बिना इसे लागू करने के अच्छे तरीके हैं। प्राइम का मूल्य

Answer 5

उन सभी उत्तरों के लिए धन्यवाद। मुझे संदेह था कि ऐसा कुछ सरल था, लेकिन मुझे उस समय यह नहीं मिला। मैंने थोड़ा और शोध भी किया है।

मैं इसे एक sieve के लिए चाहते हैं के रूप में पहले n रूढ़ अंक उत्पन्न करने के लिए, मैं सन्निकटन से अधिक या उसके n वें प्रधानमंत्री बराबर होना चाहता हूँ। (इसलिए, मैं n वें अभाज्य संख्या की ऊपरी सीमा चाहते हैं।)

Wikipedia के लिए n >= 6

p_n <= n log n + n log log n (1) 

जहां p_nn वें प्रधानमंत्री है देता ऊपरी निम्नलिखित बाध्य है, और log है प्राकृतिक लघुगणक। यह एक अच्छी शुरुआत है, लेकिन यह एक असंगत राशि से अधिक अनुमानित हो सकता है।The College Mathematics Journal में This articlen >= 7022

p_n <= n log n + n (log log n - 0.9385) (2) 

के लिए एक तंग ऊपरी बाध्य कर देता है यह एक बहुत तंग निम्न तालिका के रूप में बाध्य से पता चलता है

n   p_n   approx 1 error% approx 2 error% 
1   2        
10  29   31   6.90 
100  541   613   13.31 
1000  7919  8840  11.63 
10000  104729  114306  9.14 104921  0.18 
100000 1299709  1395639  7.38 1301789  0.16 
1000000 15485863 16441302 6.17 15502802 0.11 
10000000 179424673 188980382 5.33 179595382 0.10 

मैं अपने n वें प्रधानमंत्री सन्निकटन दूसरा सन्निकटन उपयोग करने के लिए समारोह लागू किया n >= 7022 के लिए, 6 <= n < 7022 के लिए पहला अनुमान, और पहले 5 प्रमुख संख्याओं के लिए एक सरणी लुकअप।

(हालांकि पहली विधि बहुत तंग बाध्य नहीं है, विशेष रूप से उस सीमा के लिए जहां मैं इसका उपयोग करता हूं, मुझे चिंता नहीं है क्योंकि मैं इसे चाकू के लिए चाहता हूं, और छोटी संख्याओं की चलनी कम्प्यूटेशनल रूप से सस्ते है।)

Answer 6

माई बेस्ट प्रधानमंत्री (एन) का अनुमान

1/2*(8-8.7*n-n^2+ 
1/2*(2*abs(log(n)/log(3)+log(log(n)/log(2))/log(2))+ 
abs((log(log(3))-log(log(n))+2*n*log(log(n)/log(2))+ 
sqrt(((8*log(3)*log(n))/log(2)-log(log(2))+ 
log(log(n)))*log(log(n)/log(2))))/log(log(n)/log(2))))*(-1+ 
abs(log(n)/log(3)+log(log(n)/log(2))/log(2))+abs(-(1/2)+n+ 
sqrt(((8*log(3)*log(n))/log(2)-log(log(2))+ 
log(log(n)))*log(log(n)/log(2)))/(2*log(log(n)/log(2)))))) 

यहाँ मेरी सबसे हाल ही में अधिक प्रयोगात्मक सूत्र दिया गया है। बीटीडब्ल्यू। दस ट्रिलियनवां प्राइम 323,780,508,946,331 है, यह सूत्र उस पैमाने पर काफी अच्छी तरह से काम करता है, यह सुनिश्चित नहीं है कि यह n*ln(n)+n*(ln(ln(n))-0.9385) से अधिक हो रहा है या नहीं।

1/2*(3-(8+ln(2.3))*n-n^2+1/2*(-1+ 
abs(-(1/2)+n+sqrt(ln(ln(n)/ln(2))*(-ln(ln(2))+ln(ln(n))+ 
(8*ln(3)*ln((n*ln(8*n))/ln(n)))/ln(2)))/(2*ln(ln((n*ln(8*n))/ 
ln(n))/ln(2))))+abs(ln(n)/ln(3)+ln(ln((n*ln(8*n))/ln(n))/ln(2))/ 
ln(2)))*(2*abs(ln((n*ln(8*n))/ln(n))/ln(3)+ln(ln((n*ln(8*n))/ln(n))/ 
ln(2))/ln(2))+abs(1/ln(ln(n)/ln(2))*(ln(ln(3))-ln(ln(n))+2*n*ln(ln(n)/ 
ln(2))+sqrt(((8*ln(3)*ln(n))/ln(2)-ln(ln(2))+ln(ln((n*ln(8*n))/ln(n))))* 
ln(ln((n*ln(8*n))/ln(n))/ln(2))))))) 

Answer 7

दाना जे के ऊपरी बाउंड को पूरक करने के लिए इस सूत्र को आपको एक अच्छी निचली सीमा प्रदान करनी चाहिए।

P(n) = (((2 Log(3, n + 2))/(Log(2.5, 2) + Log(3, 3)) + (2 Log(3, n - 2))/(Log(3, 2) + Log(3, 3)))/2) n;