द्विघातांकी फलन: Difference between revisions
No edit summary |
|||
| Line 19: | Line 19: | ||
* [[फर्मेट नंबर]] <math display="block">F(m) = 2^{2^m}+1</math> | * [[फर्मेट नंबर]] <math display="block">F(m) = 2^{2^m}+1</math> | ||
* सुसंगत अभाज्य संख्याएँ: अभाज्य संख्याएँ p, जिसमें क्रम 1/2 + 1/3 + 1/5 + 1/7 + ⋯ + 1/p 0, 1, 2, 3 से अधिक है।.. 0 सेप्रारंभ होने वाली पहली कुछ संख्याएँ 2, 5, 277, 5195977, ... हैं | * सुसंगत अभाज्य संख्याएँ: अभाज्य संख्याएँ p, जिसमें क्रम 1/2 + 1/3 + 1/5 + 1/7 + ⋯ + 1/p 0, 1, 2, 3 से अधिक है।.. 0 सेप्रारंभ होने वाली पहली कुछ संख्याएँ 2, 5, 277, 5195977, ... हैं | ||
* [[डबल मेर्सेन नंबर]] <math display="block">MM(p) = 2^{2^p-1}-1</math> | * [[डबल मेर्सेन नंबर|द्विमर्सीन संख्या]] <math display="block">MM(p) = 2^{2^p-1}-1</math> | ||
* सिल्वेस्टर अनुक्रम के तत्व <math display="block">s_n = \left\lfloor E^{2^{n+1}}+\frac12 \right\rfloor</math>यहां E ≈ 1.264084735305302 वर्दी का स्थिरांक है: | * सिल्वेस्टर अनुक्रम के तत्व <math display="block">s_n = \left\lfloor E^{2^{n+1}}+\frac12 \right\rfloor</math>यहां E ≈ 1.264084735305302 वर्दी का स्थिरांक है: | ||
* के-एरी [[बूलियन समारोह|बूलियन फलन]] की संख्या: <math display="block">2^{2^k}</math> | * के-एरी [[बूलियन समारोह|बूलियन फलन]] की संख्या: <math display="block">2^{2^k}</math> | ||
* अभाज्य संख्याएँ 2, 11, 1361, ... | * अभाज्य संख्याएँ 2, 11, 1361, ... <math display="block">a(n) = \left\lfloor A^{3^n}\right\rfloor</math>यहाँ A ≈ 1.306377883863 मिल्स स्थिरांक है। | ||
[[मैं अल्फ्रेड हूं|अहो]] और [[नील स्लोएन]] ने देखा कि कई महत्वपूर्ण पूर्णांक अनुक्रमों में, प्रत्येक पद एक स्थिरांक और पिछले पद का वर्ग है। वे दिखाते हैं कि ऐसे अनुक्रमों को मध्य घातांक 2 के साथ द्विघातांकी फलन के मानों को निकटतम पूर्णांक तक पूर्णांकित करके बनाया जा सकता है।<ref>{{citation|first1=A. V.|last1=Aho|author-link1=Alfred Aho|first2=N. J. A.|last2=Sloane|author-link2=N. J. A. Sloane|url=http://neilsloane.com/doc/doubly.html|title=Some doubly exponential sequences|journal=[[Fibonacci Quarterly]]|volume=11|year=1973|pages=429–437}}.</ref>आइओनास्कु और स्टैनिका एक अनुक्रम द्विघातांकी अनुक्रम और एक स्थिरांक तल के लिए कुछ और सामान्य पर्याप्त स्थितियों का वर्णन करते हैं। | |||
== अनुप्रयोग == | |||
== | === कलन विधि जटिलता === | ||
[[कम्प्यूटेशनल जटिलता सिद्धांत|संगणनात्मक जटिलता सिद्धांत]] में, द्विघातांकी वह वर्ग है जिसमें निर्णय समस्याएँ द्विघातांकी समय में हल की जा सकती हैं। यह [[EXPSPACE|एक्सस्पेस]] के समान होता है, जो एक विस्तारक ट्यूरिंग मशीन द्वारा व्यापक स्थान में हल की जा सकने वाली निर्णय समस्याओं का समुच्चय है,और यह वर्ग [[EXPSPACE|एक्सस्पेस]] के उपवर्ग है।<ref>[[Christos Papadimitriou]], Computational Complexity (1994), {{isbn|978-0-201-53082-7}}. Section 20.1, corollary 3, page 495.</ref> 2-एक्सप्टिटाइम में एक समस्या का उदाहरण जो एक्सप्टिटाइम में नहीं है, [[प्रेस्बर्गर अंकगणित]] में वाक्यांशों को सिद्ध करने या अस्वीकार करने की समस्या है।<ref>[[Michael J. Fischer|Fischer, M. J.]], and [[Michael O. Rabin]], 1974, "[http://www.lcs.mit.edu/publications/pubs/ps/MIT-LCS-TM-043.ps "Super-Exponential Complexity of Presburger Arithmetic.] {{Webarchive|url=https://web.archive.org/web/20060915010325/http://www.lcs.mit.edu/publications/pubs/ps/MIT-LCS-TM-043.ps |date=2006-09-15 }}" ''Proceedings of the SIAM-AMS Symposium in Applied Mathematics Vol. 7'': 27–41</ref> | |||
कलन विधि के आरेख और विश्लेषण में कुछ अन्य समस्याओं में, कलन विधि के विश्लेषण के अतिरिक्त इसके आरेख के अंदर द्विघातांकी अनुक्रम का उपयोग किया जाता है। एक उदाहरण है चैन का कलन विधि, जो कान्वेक्स हुल्स की गणना करने के लिए एक अनुक्रम में होने वाले परीक्षण मानों का उपयोग करता है। यह कलन विधि परीक्षण मानों hi = 22i का उपयोग करता है, और प्रत्येक परीक्षण मान के लिए समय O(n log hi) लेता है। इन परीक्षण मूल्यों की द्विघातांकी वृद्धि के कारण, अनुक्रम में प्रत्येक संगणना का समय i के कार्य के रूप में अकेले घातांकी रूप से बढ़ता है, और अनुक्रम के अंतिम चरण के लिए कुल समय का प्रभुत्व होता है। इस प्रकार,कलन विधि के लिए समग्र समय O(n log h) है जहाँ h वास्तविक आउटपुट का आकार होता है।<ref>{{citation | |||
| last = Chan | first = T. M. | author-link = Timothy M. Chan | | last = Chan | first = T. M. | author-link = Timothy M. Chan | ||
| doi = 10.1007/BF02712873 | | doi = 10.1007/BF02712873 | ||
| Line 52: | Line 41: | ||
| year = 1996| doi-access = free | | year = 1996| doi-access = free | ||
}}</ref> | }}</ref> | ||
Revision as of 11:03, 11 July 2023
एक द्विघातांकी फलन एक घातांकी फलन की घात तक बढ़ाया गया स्थिरांक है। जिसका सामान्य सूत्र है:
(यहाँ a>1 और b>1),जो एक घातांकी फलन की तुलना में बहुत तेजी से बढ़ता है। उदाहरण के लिए, यदि a = b = 10:
- f(x) = 1010x
- f(0) = 10
- f(1) = 1010
- f(2) = 10100 = "गूगोल"
- f(3) = 101000
- f(100) = 1010100 = "गूगोलप्लेक्स" .
गुणनखंड घातांकी कार्यों की तुलना में तेजी से बढ़ते हैं, परंतु द्विघातांकी कार्यों की तुलना में बहुत धीमी गति से बढ़ते हैं। यद्यपि, अनुमापन और एकरमैन फलन तेजी से बढ़ते हैं। विभिन्न कार्यों के विकास की दर की तुलना के लिए बिग ओ नोटेशन देखें।
द्विघातांकी फलन का व्युत्क्रम द्वितीय लघुगणक लॉग (लॉगx)) है।
द्विघातांकी अनुक्रम
धनात्मक पूर्णांकों या वास्तविक संख्याओं के अनुक्रम को द्विघातांकी वृद्धि दर कहा जाता है यदि अनुक्रम का nवाँ पद देने वाला फलन ऊपर और नीचे n के द्विघातांकी कार्यों द्वारा परिबद्ध है।
- फर्मेट नंबर
- सुसंगत अभाज्य संख्याएँ: अभाज्य संख्याएँ p, जिसमें क्रम 1/2 + 1/3 + 1/5 + 1/7 + ⋯ + 1/p 0, 1, 2, 3 से अधिक है।.. 0 सेप्रारंभ होने वाली पहली कुछ संख्याएँ 2, 5, 277, 5195977, ... हैं
- द्विमर्सीन संख्या
- सिल्वेस्टर अनुक्रम के तत्व यहां E ≈ 1.264084735305302 वर्दी का स्थिरांक है:
- के-एरी बूलियन फलन की संख्या:
- अभाज्य संख्याएँ 2, 11, 1361, ... यहाँ A ≈ 1.306377883863 मिल्स स्थिरांक है।
अहो और नील स्लोएन ने देखा कि कई महत्वपूर्ण पूर्णांक अनुक्रमों में, प्रत्येक पद एक स्थिरांक और पिछले पद का वर्ग है। वे दिखाते हैं कि ऐसे अनुक्रमों को मध्य घातांक 2 के साथ द्विघातांकी फलन के मानों को निकटतम पूर्णांक तक पूर्णांकित करके बनाया जा सकता है।[1]आइओनास्कु और स्टैनिका एक अनुक्रम द्विघातांकी अनुक्रम और एक स्थिरांक तल के लिए कुछ और सामान्य पर्याप्त स्थितियों का वर्णन करते हैं।
अनुप्रयोग
कलन विधि जटिलता
संगणनात्मक जटिलता सिद्धांत में, द्विघातांकी वह वर्ग है जिसमें निर्णय समस्याएँ द्विघातांकी समय में हल की जा सकती हैं। यह एक्सस्पेस के समान होता है, जो एक विस्तारक ट्यूरिंग मशीन द्वारा व्यापक स्थान में हल की जा सकने वाली निर्णय समस्याओं का समुच्चय है,और यह वर्ग एक्सस्पेस के उपवर्ग है।[2] 2-एक्सप्टिटाइम में एक समस्या का उदाहरण जो एक्सप्टिटाइम में नहीं है, प्रेस्बर्गर अंकगणित में वाक्यांशों को सिद्ध करने या अस्वीकार करने की समस्या है।[3]
कलन विधि के आरेख और विश्लेषण में कुछ अन्य समस्याओं में, कलन विधि के विश्लेषण के अतिरिक्त इसके आरेख के अंदर द्विघातांकी अनुक्रम का उपयोग किया जाता है। एक उदाहरण है चैन का कलन विधि, जो कान्वेक्स हुल्स की गणना करने के लिए एक अनुक्रम में होने वाले परीक्षण मानों का उपयोग करता है। यह कलन विधि परीक्षण मानों hi = 22i का उपयोग करता है, और प्रत्येक परीक्षण मान के लिए समय O(n log hi) लेता है। इन परीक्षण मूल्यों की द्विघातांकी वृद्धि के कारण, अनुक्रम में प्रत्येक संगणना का समय i के कार्य के रूप में अकेले घातांकी रूप से बढ़ता है, और अनुक्रम के अंतिम चरण के लिए कुल समय का प्रभुत्व होता है। इस प्रकार,कलन विधि के लिए समग्र समय O(n log h) है जहाँ h वास्तविक आउटपुट का आकार होता है।[4]
संख्या सिद्धांत
कुछ संख्या सिद्धांत सीमाएं डबल एक्सपोनेंशियल हैं। n विशिष्ट अभाज्य गुणकों वाली विषम पूर्ण संख्याएँ अधिक से अधिक ज्ञात हैं , नीलसन (2003) का एक परिणाम।[5] उत्तल पॉलीहेड्रा में के ≥ 1 पूर्णांक बिंदुओं के साथ डी-आयामी पूर्णांक जाली में एक polytope की अधिकतम मात्रा अधिकतम होती है
पिखुरको (2001) का एक परिणाम।[6] जेसीपी मिलर और डेविड व्हीलर (कंप्यूटर वैज्ञानिक) ने 1951 में EDSAC1 पर 79 अंकों का प्राइम पाया था, तब से इलेक्ट्रॉनिक युग में सबसे बड़ी ज्ञात अभाज्य संख्या मोटे तौर पर वर्ष के दोहरे घातीय कार्य के रूप में बढ़ी है।[7]
सैद्धांतिक जीव विज्ञान
जनसंख्या गतिकी में मानव जनसंख्या की वृद्धि को कभी-कभी दोहरा घातीय माना जाता है। वरफोलोमेयेव और गुरेविच[8] प्रयोगात्मक रूप से फिट
जहाँ N(y) वर्ष y में लाखों में जनसंख्या है।
भौतिकी
स्व-स्पंदन के टोडा थरथरानवाला मॉडल में, आयाम का लघुगणक समय के साथ (बड़े आयामों के लिए) चरघातांकी रूप से भिन्न होता है, इस प्रकार आयाम समय के दोगुने घातीय फलन के रूप में भिन्न होता है।[9] डेन्ड्रिटिक मैक्रो मोलेक्यूल्स को दोगुने-घातीय तरीके से बढ़ने के लिए देखा गया है।[10]
संदर्भ
- ↑ Aho, A. V.; Sloane, N. J. A. (1973), "Some doubly exponential sequences", Fibonacci Quarterly, 11: 429–437.
- ↑ Christos Papadimitriou, Computational Complexity (1994), ISBN 978-0-201-53082-7. Section 20.1, corollary 3, page 495.
- ↑ Fischer, M. J., and Michael O. Rabin, 1974, ""Super-Exponential Complexity of Presburger Arithmetic. Archived 2006-09-15 at the Wayback Machine" Proceedings of the SIAM-AMS Symposium in Applied Mathematics Vol. 7: 27–41
- ↑ Chan, T. M. (1996), "Optimal output-sensitive convex hull algorithms in two and three dimensions", Discrete and Computational Geometry, 16 (4): 361–368, doi:10.1007/BF02712873, MR 1414961
- ↑ Nielsen, Pace P. (2003), "An upper bound for odd perfect numbers", INTEGERS: The Electronic Journal of Combinatorial Number Theory, 3: A14.
- ↑ Pikhurko, Oleg (2001), "Lattice points in lattice polytopes", Mathematika, 48 (1–2): 15–24, arXiv:math/0008028, Bibcode:2000math......8028P, doi:10.1112/s0025579300014339
- ↑ Miller, J. C. P.; Wheeler, D. J. (1951), "Large prime numbers", Nature, 168 (4280): 838, Bibcode:1951Natur.168..838M, doi:10.1038/168838b0.
- ↑ Varfolomeyev, S. D.; Gurevich, K. G. (2001), "The hyperexponential growth of the human population on a macrohistorical scale", Journal of Theoretical Biology, 212 (3): 367–372, Bibcode:2001JThBi.212..367V, doi:10.1006/jtbi.2001.2384, PMID 11829357.
- ↑ Kouznetsov, D.; Bisson, J.-F.; Li, J.; Ueda, K. (2007), "Self-pulsing laser as oscillator Toda: Approximation through elementary functions", Journal of Physics A, 40 (9): 1–18, Bibcode:2007JPhA...40.2107K, doi:10.1088/1751-8113/40/9/016, S2CID 53330023.
- ↑ Kawaguchi, Tohru; Walker, Kathleen L.; Wilkins, Charles L.; Moore, Jeffrey S. (1995). "Double Exponential Dendrimer Growth". Journal of the American Chemical Society. 117 (8): 2159–2165. doi:10.1021/ja00113a005.
