पेरिन संख्या

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

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 के लिए एनवें पेरिन संख्या द्वारा गिना जाता है.

इतिहास

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

गुण

सृजन फलन

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

$G(P(n);x)={\frac {3-x^{2}}{1-x^{2}-x^{3}}}.$

आव्यूह सूत्र

${\begin{pmatrix}0&1&0\\0&0&1\\1&1&0\end{pmatrix}}^{\!n}{\begin{pmatrix}3\\0\\2\end{pmatrix}}={\begin{pmatrix}P\left(n\right)\\P\left(n+1\right)\\P\left(n+2\right)\end{pmatrix}}$

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

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

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

$x^{3}-x-1=0.$

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

$P(n)=p^{n}+q^{n}+r^{n}.$

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

$P(n)\approx p^{n}$

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

गुणन सूत्र

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

${\begin{matrix}G(n-1)&=&p^{-1}p^{n}+&q^{-1}q^{n}+&r^{-1}r^{n}\\G(n)&=&p^{n}+&q^{n}+&r^{n}\\G(n+1)&=&pp^{n}+&qq^{n}+&rr^{n}\end{matrix}}$

जो की हमें विभाजन क्षेत्र पर गुणांकों के साथ रैखिक समीकरणों की तीन प्रणालियाँ देता है $x^{3}-x-1$; और व्युत्क्रमणीय आव्यूह द्वारा आव्यूह (गणित) जिसे हम हल कर सकते हैं $p^{n},q^{n},r^{n}$ और फिर हम उन्हें kth घात तक बढ़ा सकते हैं और योग की गणना कर सकते हैं।

उदाहरण मैग्मा कंप्यूटर बीजगणित प्रणाली कोड:

P<x> := PolynomialRing(Rationals());
S<t> := SplittingField(x^3-x-1);
P2<y> := PolynomialRing(S);
p,q,r := Explode([r[1] : r in Roots(y^3-y-1)]);
Mi:=Matrix([[1/p,1/q,1/r],[1,1,1],[p,q,r]])^(-1);
T<u,v,w> := PolynomialRing(S,3);
v1 := ChangeRing(Mi,T) *Matrix([[u],[v],[w]]);
[p^i*v1[1,1]^3 + q^i*v1[2,1]^3 + r^i*v1[3,1]^3 : i in [-1..1]];

$u=G(n-1),v=G(n),w=G(n+1)$ परिणाम के साथ, यदि हमारे पास है , तब

${\begin{matrix}23G(2n-1)&=&4u^{2}+3v^{2}+9w^{2}+18uv-12uw-4vw\\23G(2n)&=&-6u^{2}+7v^{2}-2w^{2}-4uv+18uw+6vw\\23G(2n+1)&=&9u^{2}+v^{2}+3w^{2}+6uv-4uw+14vw\\23G(3n-1)&=&\left(-4u^{3}+2v^{3}-w^{3}+9(uv^{2}+vw^{2}+wu^{2})+3v^{2}w+6uvw\right)\\23G(3n)&=&\left(3u^{3}+2v^{3}+3w^{3}-3(uv^{2}+uw^{2}+vw^{2}+vu^{2})+6v^{2}w+18uvw\right)\\23G(3n+1)&=&\left(v^{3}-w^{3}+6uv^{2}+9uw^{2}+6vw^{2}+9vu^{2}-3wu^{2}+6wv^{2}-6uvw\right)\end{matrix}}$

जहाँ संख्या 23 अनुक्रम के परिभाषित बहुपद के विवेचक या डिग्री 3 से उत्पन्न होती है।

यह पूर्णांक अंकगणित का उपयोग करके nth पेरिन संख्या की गणना की अनुमति देता है तथा $O(\log 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, ... (sequence A013998 in the OEIS)

चूंकि पेरिन स्यूडोप्राइम्स के अस्तित्व के प्रश्न पर स्वयं पेरिन ने विचार किया था, किन्तु यह ज्ञात नहीं था कि एडम्स और शैंक्स (1982) द्वारा अधिक छोटे छद्मप्राइम्स की खोज किए जाने तक यह अस्तित्व में थे या नहीं, 271441 = 521²; इसके पश्चात यह अधिक छोटा 904631 = 7 × 13 × 9941 है। उनमें से सत्रह अरब से घट जाते हैं; और जॉन ग्रांथम ने प्रमाणित कर दिया है कि पेरिन छद्मप्राइम्स अनंत रूप से कई हैं।

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

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

पेरिन अभाज्य

पेरिन अभाज्य पेरिन संख्या है जो अभाज्य संख्या है। पहले कुछ पेरिन अभाज्य हैं:

2, 3, 5, 7, 17, 29, 277, 367, 853, 14197, 43721, 1442968193, 792606555396977, 187278659180417234321, 66241160488780141071 579864797, ... (sequence A074788 in the OEIS)

इन पेरिन अभाज्यों के लिए, सूचकांक n का P(n) है

2, 3, 4, 5, 6, 7, 10, 12, 20, 21, 24, 34, 38, 75, 122, 166, 236, 355, 356, 930, 1042, 1214, 1461, 1622, 4430 , 5802, 9092, ... (sequence A112881 in the OEIS)

P(n) उत्पन्न करना जहां n ऋणात्मक पूर्णांक है, मौलिकता के संबंध में समान गुण उत्पन्न करता है: यदि n ऋणात्मक है, तो P(n) अभाज्य है जब P(n) mod −n = −n − 1. निम्नलिखित अनुक्रम P का प्रतिनिधित्व करता है (n) उन सभी n के लिए जो ऋणात्मक पूर्णांक हैं:

−1, 1, 2, −3, 4, −2, −1, 5, −7, 6, −1, −6, 12, −13, 7, 5, −18, 25, −20, 2 , 23, −43, 45, −22, −21, 66, −88, 67, −1, ... (sequence A078712 in the OEIS)

संदर्भ

• Füredi, Zoltán (1987). "The number of maximal independent sets in connected graphs". Journal of Graph Theory. 11 (4): 463–470. doi:10.1002/jgt.3190110403.

• Knuth, Donald E. (2011). The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. Addison-Wesley. ISBN 978-0201038040.

• Grantham, Jon (2010). "There are infinitely many Perrin pseudoprimes" (PDF). Journal of Number Theory. 130 (5): 1117–1128. arXiv:1903.06825. doi:10.1016/j.jnt.2009.11.008. S2CID 13935283.

अग्रिम पठन

• Adams, William; Shanks, Daniel (1982). "Strong primality tests that are not sufficient". Mathematics of Computation. American Mathematical Society. 39 (159): 255–300. doi:10.2307/2007637. JSTOR 2007637. MR 0658231.

• Perrin, R. (1899). "Query 1484". L'Intermédiaire des Mathématiciens. 6: 76.

• Lucas, E. (1878). "Théorie des fonctions numériques simplement périodiques". American Journal of Mathematics. The Johns Hopkins University Press. 1 (3): 197–240. doi:10.2307/2369311. JSTOR 2369311.

बाहरी संबंध

• Zentrum für Hirnforschung Institut für Medizinische Kybernetik und Artificial Intelligence
• "Lucas Pseudoprimes". MathPages.com.
• "Perrin's Sequence". MathPages.com.
• OEIS sequence A225876 (Composite n which divide s(n)+1, where s is ...)—Perrin-like sequence
• Perrin Primality Tests