पेरिन संख्या: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 6: Line 6:
:{{math|1=''P''(0) = 3, ''P''(1) = 0, ''P''(2) = 2}}.
:{{math|1=''P''(0) = 3, ''P''(1) = 0, ''P''(2) = 2}}.


पेरिन संख्याओं का पूर्णांक अनुक्रम प्रारंभ होता है
पेरिन संख्याओं का पूर्णांक अनुक्रम प्रारंभ होता है
:[[3 (संख्या)]], [[0 (संख्या)]], [[2 (संख्या)]], 3, 2, [[5 (संख्या)]], 5, [[7 (संख्या)]], [[10 (संख्या)]], [[12 (संख्या)]], [[17 (संख्या)]], 22 (संख्या ), [[29 (संख्या)]], [[39 (संख्या)]], ... {{OEIS|id=A001608}}
:[[3 (संख्या)]], [[0 (संख्या)]], [[2 (संख्या)]], 3, 2, [[5 (संख्या)]], 5, [[7 (संख्या)]], [[10 (संख्या)]], [[12 (संख्या)]], [[17 (संख्या)]], 22 (संख्या ), [[29 (संख्या)]], [[39 (संख्या)]], ... {{OEIS|id=A001608}}


{{math|''n''}}-वर्टेक्स [[चक्र ग्राफ]] में विभिन्न [[अधिकतम स्वतंत्र सेट|अधिकतम स्वतंत्र समुच्चय]] की संख्या को {{math|''n'' > 1}} के लिए एनवें पेरिन संख्या द्वारा गिना जाता है.<ref>{{harvtxt|Füredi|1987}}</ref>
{{math|''n''}}-वर्टेक्स [[चक्र ग्राफ]] में विभिन्न [[अधिकतम स्वतंत्र सेट|अधिकतम स्वतंत्र समुच्चय]] की संख्या को {{math|''n'' > 1}} के लिए एनवें पेरिन संख्या द्वारा गिना जाता है.<ref>{{harvtxt|Füredi|1987}}</ref>


==इतिहास==
==इतिहास==
इस प्रकार से क्रम का उल्लेख एडौर्ड लुकास (1876) द्वारा स्पष्ट रूप से किया गया था। और 1899 में, इसी क्रम का स्पष्ट रूप से उल्लेख फ्रांकोइस ओलिवर राउल पेरिन द्वारा किया गया था।<ref>{{harvtxt|Knuth|2011}}</ref> इस क्रम का अधिक व्यापक उपचार एडम्स और शैंक्स (1982) द्वारा दिया गया था।
इस प्रकार से क्रम का उल्लेख एडौर्ड लुकास (1876) द्वारा स्पष्ट रूप से किया गया था। और 1899 में, इसी क्रम का स्पष्ट रूप से उल्लेख फ्रांकोइस ओलिवर राउल पेरिन द्वारा किया गया था।<ref>{{harvtxt|Knuth|2011}}</ref> इस क्रम का अधिक व्यापक उपचार एडम्स और शैंक्स (1982) द्वारा दिया गया था।


==गुण==
==गुण==


===सृजन फलन ===
===सृजन फलन ===
पेरिन अनुक्रम का जनक फलन है
पेरिन अनुक्रम का जनक फलन है


:<math>G(P(n);x) = \frac{3-x^2}{1-x^2-x^3}.</math>
:<math>G(P(n);x) = \frac{3-x^2}{1-x^2-x^3}.</math>
===आव्यूह सूत्र===
===आव्यूह सूत्र===
:<math>\begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}^{\!n}
:<math>\begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}^{\!n}
   \begin{pmatrix} 3 \\ 0 \\ 2 \end{pmatrix} =
   \begin{pmatrix} 3 \\ 0 \\ 2 \end{pmatrix} =
Line 28: Line 28:


:<math>x^3 - x - 1 = 0.</math>
:<math>x^3 - x - 1 = 0.</math>
इस समीकरण के 3 मूल होते हैं; और [[वास्तविक संख्या]] मूल p (प्लास्टिक संख्या के रूप में जाना जाता है) और दो जटिल संयुग्मी मूल q और r। इन तीन रूट को देखते हुए यह दर्शाया गया है , की [[लुकास अनुक्रम]] बिनेट सूत्र का पेरिन अनुक्रम एनालॉग है
इस समीकरण के 3 मूल होते हैं; और [[वास्तविक संख्या]] मूल p (प्लास्टिक संख्या के रूप में जाना जाता है) और दो जटिल संयुग्मी मूल q और r। इन तीन रूट को देखते हुए यह दर्शाया गया है , की [[लुकास अनुक्रम]] बिनेट सूत्र का पेरिन अनुक्रम एनालॉग है


:<math>P(n) = p^n + q^n + r^n.</math>
:<math>P(n) = p^n + q^n + r^n.</math>
चूँकि सम्मिश्र संख्या मूल q और r दोनों का निरपेक्ष मान 1 से घट जाता है, इन मूलों की पॉवर उच्च n के लिए अनुक्रम 0 की सीमा तय करती हैं। उच्च n के लिए सूत्र घट जाती है
चूँकि सम्मिश्र संख्या मूल q और r दोनों का निरपेक्ष मान 1 से घट जाता है, इन मूलों की पॉवर उच्च n के लिए अनुक्रम 0 की सीमा तय करती हैं। उच्च n के लिए सूत्र घट जाती है


:<math>P(n) \approx p^n                              </math>
:<math>P(n) \approx p^n                              </math>
अतः इस सूत्र का उपयोग उच्च n के लिए पेरिन अनुक्रम के मानों की त्वरित गणना करने के लिए किया जा सकता है। और पेरिन अनुक्रम में क्रमिक पदों का अनुपात p, अर्थात प्लास्टिक संख्या के समीप पहुंचता है, जिसका मान लगभग 1.324718 है। यह स्थिरांक पेरिन अनुक्रम से यह संबंध रखता है जो की स्वर्णिम अनुपात लुकास संख्या क्र रूप में किया जाता है। इसी प्रकार के संबंध ''p'' और पाडोवन अनुक्रम के मध्य होते है , और सुनहरे अनुपात और फाइबोनैचि संख्याओं के मध्य होते है , और चांदी अनुपात और पेल संख्याओं के मध्य भी उपस्तिथ होते हैं।
अतः इस सूत्र का उपयोग उच्च n के लिए पेरिन अनुक्रम के मानों की त्वरित गणना करने के लिए किया जा सकता है। और पेरिन अनुक्रम में क्रमिक पदों का अनुपात p, अर्थात प्लास्टिक संख्या के समीप पहुंचता है, जिसका मान लगभग 1.324718 है। यह स्थिरांक पेरिन अनुक्रम से यह संबंध रखता है जो की स्वर्णिम अनुपात लुकास संख्या क्र रूप में किया जाता है। इसी प्रकार के संबंध ''p'' और पाडोवन अनुक्रम के मध्य होते है , और सुनहरे अनुपात और फाइबोनैचि संख्याओं के मध्य होते है , और चांदी अनुपात और पेल संख्याओं के मध्य भी उपस्तिथ होते हैं।


===गुणन सूत्र===
===गुणन सूत्र===
Line 43: Line 43:
G(n) & =& p^n+&q^n+&r^n\\
G(n) & =& p^n+&q^n+&r^n\\
G(n+1) &=& pp^n +& qq^n +& rr^n\end{matrix}                                                                                                                                        </math>
G(n+1) &=& pp^n +& qq^n +& rr^n\end{matrix}                                                                                                                                        </math>
जो की हमें [[विभाजन क्षेत्र]] पर गुणांकों के साथ रैखिक समीकरणों की तीन प्रणालियाँ देता है <math>x^3 -x -1                                                                                                                                                                                </math>; और व्युत्क्रमणीय आव्यूह द्वारा [[मैट्रिक्स (गणित)|आव्यूह (गणित)]] जिसे हम हल कर सकते हैं <math>p^n, q^n, r^n</math> और फिर हम उन्हें ''k''th घात तक बढ़ा सकते हैं और योग की गणना कर सकते हैं।
जो की हमें [[विभाजन क्षेत्र]] पर गुणांकों के साथ रैखिक समीकरणों की तीन प्रणालियाँ देता है <math>x^3 -x -1                                                                                                                                                                                </math>; और व्युत्क्रमणीय आव्यूह द्वारा [[मैट्रिक्स (गणित)|आव्यूह (गणित)]] जिसे हम हल कर सकते हैं <math>p^n, q^n, r^n</math> और फिर हम उन्हें ''k''th घात तक बढ़ा सकते हैं और योग की गणना कर सकते हैं।


उदाहरण [[मैग्मा कंप्यूटर बीजगणित प्रणाली]] कोड:<syntaxhighlight>
उदाहरण [[मैग्मा कंप्यूटर बीजगणित प्रणाली]] कोड:<syntaxhighlight>
Line 65: Line 65:
23G(3n+1)& = &\left(v^3-w^3+6uv^2+9uw^2+6vw^2+9vu^2-3wu^2+6wv^2-6uvw\right) \end{matrix}
23G(3n+1)& = &\left(v^3-w^3+6uv^2+9uw^2+6vw^2+9vu^2-3wu^2+6wv^2-6uvw\right) \end{matrix}
</math>
</math>
जहाँ संख्या 23 अनुक्रम के परिभाषित [[बहुपद]] के विवेचक या डिग्री 3 से उत्पन्न होती है।
जहाँ संख्या 23 अनुक्रम के परिभाषित [[बहुपद]] के विवेचक या डिग्री 3 से उत्पन्न होती है।


यह [[पूर्णांक]] अंकगणित का उपयोग करके ''n''th पेरिन संख्या की गणना की अनुमति देता है तथा <math>O(\log n)</math> गुणा करता है.  
यह [[पूर्णांक]] अंकगणित का उपयोग करके ''n''th पेरिन संख्या की गणना की अनुमति देता है तथा <math>O(\log n)</math> गुणा करता है.  


==अभाज्य और विभाज्यता==
==अभाज्य और विभाज्यता==
Line 73: Line 73:
===पेरिन [[स्यूडोप्राइम]]===
===पेरिन [[स्यूडोप्राइम]]===


इस प्रकार से यह [[गणितीय प्रमाण]] है कि सभी [[अभाज्य संख्या]] p के लिए, ''p, P(p)'' को विभाजित करता है। चूंकि , विपरीत (तर्क) सत्य नहीं है: कुछ मिश्रित संख्याओं n के लिए, n अभी भी ''P(n)'' को विभाजित कर सकता है। यदि n में यह गुण है, तो इसे पेरिन स्यूडोप्राइम कहा जाता है।
इस प्रकार से यह [[गणितीय प्रमाण]] है कि सभी [[अभाज्य संख्या]] p के लिए, ''p, P(p)'' को विभाजित करता है। चूंकि , विपरीत (तर्क) सत्य नहीं है: कुछ मिश्रित संख्याओं n के लिए, n अभी भी ''P(n)'' को विभाजित कर सकता है। यदि n में यह गुण है, तो इसे पेरिन स्यूडोप्राइम कहा जाता है।


अतः पहले कुछ पेरिन स्यूडोप्राइम इस प्रकार हैं
अतः पहले कुछ पेरिन स्यूडोप्राइम इस प्रकार हैं
:271441, 904631, 16532714, 24658561, 27422714, 27664033, 46672291, 102690901, 130944133, 196075949, 214038533, 517697641, 545670533, 801123451, 855073301, 903136901, 970355431, ... {{OEIS|id=A013998}}
:271441, 904631, 16532714, 24658561, 27422714, 27664033, 46672291, 102690901, 130944133, 196075949, 214038533, 517697641, 545670533, 801123451, 855073301, 903136901, 970355431, ... {{OEIS|id=A013998}}


चूंकि पेरिन स्यूडोप्राइम्स के अस्तित्व के प्रश्न पर स्वयं पेरिन ने विचार किया था, किन्तु यह ज्ञात नहीं था कि एडम्स और शैंक्स (1982) द्वारा अधिक छोटे छद्मप्राइम्स की खोज किए जाने तक यह अस्तित्व में थे या नहीं, 271441 = 521<sup>2</sup>; इसके पश्चात यह अधिक छोटा 904631 = 7 × 13 × 9941 है। उनमें से सत्रह अरब से घट जाते हैं;<ref>{{OEIS|id=A013998}}</ref> और जॉन ग्रांथम ने प्रमाणित कर दिया है कि पेरिन छद्मप्राइम्स अनंत रूप से कई हैं।<ref>{{harvtxt|Grantham|2010}}</ref>
चूंकि पेरिन स्यूडोप्राइम्स के अस्तित्व के प्रश्न पर स्वयं पेरिन ने विचार किया था, किन्तु यह ज्ञात नहीं था कि एडम्स और शैंक्स (1982) द्वारा अधिक छोटे छद्मप्राइम्स की खोज किए जाने तक यह अस्तित्व में थे या नहीं, 271441 = 521<sup>2</sup>; इसके पश्चात यह अधिक छोटा 904631 = 7 × 13 × 9941 है। उनमें से सत्रह अरब से घट जाते हैं;<ref>{{OEIS|id=A013998}}</ref> और जॉन ग्रांथम ने प्रमाणित कर दिया है कि पेरिन छद्मप्राइम्स अनंत रूप से कई हैं।<ref>{{harvtxt|Grantham|2010}}</ref>


अतः एडम्स और शैंक्स (1982) ने कहा कि अभाज्य संख्याएँ भी इस नियम को पूर्ण करती हैं कि P(−p) = −1 mod p. ऐसे कंपोजिट जहां दोनों गुण उपस्तिथ होते हैं, और प्रतिबंधित पेरिन स्यूडोप्राइम कहलाते हैं {{OEIS|id=A018187}}. आगे की नियम को ''n'' के छह अवयव हस्ताक्षर का उपयोग करके प्रयुक्त किया जा सकता है जो तीन रूपों में से होना चाहिए (उदाहरण के लिए) {{OEIS2C|A275612}} और {{OEIS2C|A275613}}).
अतः एडम्स और शैंक्स (1982) ने कहा कि अभाज्य संख्याएँ भी इस नियम को पूर्ण करती हैं कि P(−p) = −1 mod p. ऐसे कंपोजिट जहां दोनों गुण उपस्तिथ होते हैं, और प्रतिबंधित पेरिन स्यूडोप्राइम कहलाते हैं {{OEIS|id=A018187}}. आगे की नियम को ''n'' के छह अवयव हस्ताक्षर का उपयोग करके प्रयुक्त किया जा सकता है जो तीन रूपों में से होना चाहिए (उदाहरण के लिए) {{OEIS2C|A275612}} और {{OEIS2C|A275613}}).


जबकि पेरिन स्यूडोप्राइम दुर्लभ हैं, उनका [[फ़र्मेट स्यूडोप्राइम]] के साथ महत्वपूर्ण ओवरलैप है। यह [[लुकास स्यूडोप्राइम]] के विपरीत है जो सहसंबद्ध विरोधी हैं। इसके पश्चात स्थिति का उपयोग लोकप्रिय, कुशल और अधिक प्रभावी बैली-पीएसडब्ल्यू प्राइमलिटी परीक्षण प्राप्त करने के लिए किया जाता है, जिसमें कोई ज्ञात छद्मप्राइम नहीं होता है, और अधिक छोटा 2<sup>64</sup> से बड़ा माना जाता है।.
जबकि पेरिन स्यूडोप्राइम दुर्लभ हैं, उनका [[फ़र्मेट स्यूडोप्राइम]] के साथ महत्वपूर्ण ओवरलैप है। यह [[लुकास स्यूडोप्राइम]] के विपरीत है जो सहसंबद्ध विरोधी हैं। इसके पश्चात स्थिति का उपयोग लोकप्रिय, कुशल और अधिक प्रभावी बैली-पीएसडब्ल्यू प्राइमलिटी परीक्षण प्राप्त करने के लिए किया जाता है, जिसमें कोई ज्ञात छद्मप्राइम नहीं होता है, और अधिक छोटा 2<sup>64</sup> से बड़ा माना जाता है।.


===पेरिन अभाज्य===
===पेरिन अभाज्य===

Revision as of 12:21, 13 July 2023

गणित में, पेरिन संख्याओं को पुनरावृत्ति संबंध द्वारा परिभाषित किया जाता है

P(n) = P(n − 2) + P(n − 3) के लिए n > 2,

प्रारंभिक मूल्यों के साथ:

P(0) = 3, P(1) = 0, P(2) = 2.

पेरिन संख्याओं का पूर्णांक अनुक्रम प्रारंभ होता है

3 (संख्या), 0 (संख्या), 2 (संख्या), 3, 2, 5 (संख्या), 5, 7 (संख्या), 10 (संख्या), 12 (संख्या), 17 (संख्या), 22 (संख्या ), 29 (संख्या), 39 (संख्या), ... (sequence A001608 in the OEIS)

n-वर्टेक्स चक्र ग्राफ में विभिन्न अधिकतम स्वतंत्र समुच्चय की संख्या को n > 1 के लिए एनवें पेरिन संख्या द्वारा गिना जाता है.[1]

इतिहास

इस प्रकार से क्रम का उल्लेख एडौर्ड लुकास (1876) द्वारा स्पष्ट रूप से किया गया था। और 1899 में, इसी क्रम का स्पष्ट रूप से उल्लेख फ्रांकोइस ओलिवर राउल पेरिन द्वारा किया गया था।[2] इस क्रम का अधिक व्यापक उपचार एडम्स और शैंक्स (1982) द्वारा दिया गया था।

गुण

सृजन फलन

पेरिन अनुक्रम का जनक फलन है

आव्यूह सूत्र

बिनेट जैसा सूत्र

भुजाओं की लंबाई वाले समबाहु त्रिभुजों का सर्पिल जो पेरिन अनुक्रम का अनुसरण करता है।

इस प्रकार से पेरिन संख्याओं को समीकरण के बहुपद के मूल की घातों के रूप में लिखा जा सकता है

इस समीकरण के 3 मूल होते हैं; और वास्तविक संख्या मूल p (प्लास्टिक संख्या के रूप में जाना जाता है) और दो जटिल संयुग्मी मूल q और r। इन तीन रूट को देखते हुए यह दर्शाया गया है , की लुकास अनुक्रम बिनेट सूत्र का पेरिन अनुक्रम एनालॉग है

चूँकि सम्मिश्र संख्या मूल q और r दोनों का निरपेक्ष मान 1 से घट जाता है, इन मूलों की पॉवर उच्च n के लिए अनुक्रम 0 की सीमा तय करती हैं। उच्च n के लिए सूत्र घट जाती है

अतः इस सूत्र का उपयोग उच्च n के लिए पेरिन अनुक्रम के मानों की त्वरित गणना करने के लिए किया जा सकता है। और पेरिन अनुक्रम में क्रमिक पदों का अनुपात p, अर्थात प्लास्टिक संख्या के समीप पहुंचता है, जिसका मान लगभग 1.324718 है। यह स्थिरांक पेरिन अनुक्रम से यह संबंध रखता है जो की स्वर्णिम अनुपात लुकास संख्या क्र रूप में किया जाता है। इसी प्रकार के संबंध p और पाडोवन अनुक्रम के मध्य होते है , और सुनहरे अनुपात और फाइबोनैचि संख्याओं के मध्य होते है , और चांदी अनुपात और पेल संख्याओं के मध्य भी उपस्तिथ होते हैं।

गुणन सूत्र

इस प्रकार से बिनेट सूत्र से, हम G(n − 1), G(n) और G(n+ 1) के संदर्भ में G(kn) के लिए सूत्र प्राप्त कर सकते हैं; हम जानते हैं