मिस्र के भिन्नों के लिए ग्रीडी एल्गोरिदम

गणित में, मिस्र के भिन्नों के लिए लालची एल्गोरिथ्म एक लालची एल्गोरिदम है, जिसे सबसे पहले फाइबोनैचि द्वारा मिस्र के भिन्नों में तर्कसंगत संख्याओं को बदलने के लिए वर्णित किया गया था। मिस्र का भिन्न भिन्न इकाई भिन्नों के योग के रूप में एक अपरिवर्तनीय भिन्न का प्रतिनिधित्व करता है, जैसे 5/6 = 1/2 + 1/3. जैसा कि नाम से संकेत मिलता है, इन अभ्यावेदनों का उपयोग बहुत पहले मिस्र के गणित के रूप में किया गया था, लेकिन इस तरह के विस्तार के निर्माण के लिए पहली प्रकाशित व्यवस्थित विधि का वर्णन 1202 में पीसा के लियोनार्डो (फाइबोनैचि) के अबेकस की किताब में किया गया था। इसे लालची एल्गोरिदम कहा जाता है क्योंकि प्रत्येक चरण में एल्गोरिदम लालच से सबसे बड़ा संभव इकाई अंश चुनता है जिसका उपयोग शेष अंश के किसी भी प्रतिनिधित्व में किया जा सकता है।

फाइबोनैचि वास्तव में मिस्र के अंश प्रतिनिधित्व के निर्माण के लिए कई अलग-अलग तरीकों को सूचीबद्ध करता है। वह उन स्थितियों के लिए अंतिम उपाय के रूप में लालची विधि को शामिल करता है जब कई सरल विधियां विफल हो जाती हैं; इन विधियों की अधिक विस्तृत सूची के लिए मिस्री अंश देखें। जैसा कि साल्ज़र (1948) ने विवरण दिया है, अपरिमेय संख्याओं के सन्निकटन के लिए लालची विधि और इसके विस्तार को आधुनिक गणितज्ञों द्वारा कई बार फिर से खोजा गया है, सबसे पहले और सबसे उल्लेखनीय रूप से J. J. Sylvester (1880) एक निकट से संबंधित विस्तार विधि जो योग में कुछ इकाई अंशों को ऋणात्मक होने की अनुमति देकर प्रत्येक चरण पर निकट सन्निकटन उत्पन्न करती है, जो पहले की है Lambert (1770).

किसी संख्या के लिए इस विधि द्वारा उत्पन्न विस्तार $x$ लालची मिस्री विस्तार, सिल्वेस्टर विस्तार, या फाइबोनैचि-सिल्वेस्टर विस्तार कहा जाता है $x$. हालाँकि, फाइबोनैचि विस्तार शब्द आमतौर पर इस पद्धति को नहीं, बल्कि फाइबोनैचि संख्याओं के योग के रूप में पूर्णांकों के प्रतिनिधित्व को संदर्भित करता है।

एल्गोरिदम और उदाहरण

फाइबोनैचि का एल्गोरिदम अंश का विस्तार करता है $x/y$ बार-बार प्रतिस्थापन करके, प्रतिनिधित्व किया जाना

$${\frac {x}{y}}={\frac {1}{\left\lceil {\frac {y}{x}}\right\rceil }}+{\frac {(-y){\bmod {x}}}{y\left\lceil {\frac {y}{x}}\right\rceil }}$$

(आवश्यकतानुसार इस प्रतिस्थापन में दूसरे पद को सरल बनाना)। उदाहरण के लिए:

$${\frac {7}{15}}={\frac {1}{3}}+{\frac {2}{15}}={\frac {1}{3}}+{\frac {1}{8}}+{\frac {1}{120}}.$$

इस विस्तार में, पहली इकाई भिन्न का हर 3 पूर्णांकन का परिणाम है 15/7 अगले बड़े पूर्णांक तक, और शेष भिन्न तक 2/15सरलीकरण का परिणाम है −15 mod 7/15 × 3 = 6/45. दूसरी इकाई भिन्न का हर, 8, पूर्णांकन का परिणाम है 15/2 अगले बड़े पूर्णांक तक, और शेष भिन्न तक 1/120 वही है जो बचा हुआ है 7/15दोनों को घटाने के बाद 1/3 और 1/8.

चूंकि प्रत्येक विस्तार चरण विस्तारित किए जाने वाले शेष अंश के अंश को कम कर देता है, यह विधि हमेशा एक सीमित विस्तार के साथ समाप्त होती है; हालाँकि, प्राचीन मिस्र के विस्तार या अधिक आधुनिक तरीकों की तुलना में, यह विधि बड़े हर के साथ काफी लंबे विस्तार उत्पन्न कर सकती है। उदाहरण के लिए, यह विधि विस्तारित होती है

$${\frac {5}{121}}={\frac {1}{25}}+{\frac {1}{757}}+{\frac {1}{763\,309}}+{\frac {1}{873\,960\,180\,913}}+{\frac {1}{1\,527\,612\,795\,642\,093\,418\,846\,225}},$$

जबकि अन्य तरीकों से काफी बेहतर विस्तार होता है

$${\frac {5}{121}}={\frac {1}{33}}+{\frac {1}{121}}+{\frac {1}{363}}.$$

Wagon (1991) इससे भी अधिक बुरे व्यवहार वाला उदाहरण सुझाता है, 31/311. लालची विधि दस पदों के साथ विस्तार की ओर ले जाती है, जिनमें से अंतिम के हर में 500 से अधिक अंक होते हैं; हालाँकि, 31/311 का गैर-लालची प्रतिनिधित्व बहुत छोटा है, 1/12 + 1/63 + 1/2799 + 1/8708.

सिल्वेस्टर का अनुक्रम और निकटतम सन्निकटन

सिल्वेस्टर का अनुक्रम 2, 3, 7, 43, 1807, ... (OEIS: A000058) को संख्या 1 के लिए इस प्रकार के अनंत लालची विस्तार द्वारा उत्पन्न के रूप में देखा जा सकता है, जहां प्रत्येक चरण में हम हर को चुनते हैं ⌊ y/x ⌋ + 1 के बजाय ⌈ y/x ⌉. इस अनुक्रम को k पदों में छोटा करना और संगत मिस्री अंश बनाना, उदाहरणार्थ (k=4 के लिए)

$${\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{7}}+{\frac {1}{43}}={\frac {1805}{1806}}$$

किसी भी k-टर्म मिस्री अंश द्वारा 1 के निकटतम संभावित कम अनुमान का परिणाम होता है। उदाहरण के लिए, खुले अंतराल में किसी संख्या के लिए कोई मिस्री अंश (1805/1806, 1) कम से कम पांच शब्दों की आवश्यकता है। Curtiss (1922) एक पूर्ण संख्या के विभाजकों की संख्या को कम करने में इन निकटतम-अनुमान परिणामों के अनुप्रयोग का वर्णन करता है, जबकि Stong (1983) समूह सिद्धांत में अनुप्रयोगों का वर्णन करता है।

अधिकतम-लंबाई विस्तार और सर्वांगसमता स्थितियाँ

कोई भी अंश x/y को अपने लालची विस्तार में अधिकतम x पदों की आवश्यकता होती है। Mays (1987) और Freitag & Phillips (1999) उन परिस्थितियों की जांच करें जिनके तहत लालची पद्धति का विस्तार उत्पन्न होता है x/y बिल्कुल x पदों के साथ; इन्हें y पर सर्वांगसमता स्थितियों के संदर्भ में वर्णित किया जा सकता है।

• हर अंश 1/y इसके लालची विस्तार में एक पद की आवश्यकता है; ऐसा सबसे सरल भिन्न है 1/1.
• हर अंश 2/y को इसके लालची विस्तार में दो शब्दों की आवश्यकता होती है यदि और केवल यदि y ≡ 1 (mod 2); ऐसा सबसे सरल भिन्न है 2/3.
• एक अंश 3/y को इसके लालची विस्तार में तीन शब्दों की आवश्यकता होती है यदि और केवल यदि y ≡ 1 (mod 6), तब के लिए −y mod x = 2 और y(y + 2)/3 विषम है, इसलिए लालची विस्तार के एक चरण के बाद शेष अंश,
  $${\frac {(-y){\bmod {x}}}{y\left\lceil {\frac {y}{x}}\right\rceil }}={\frac {2}{\,{\frac {y(y+2)}{3}}\,}}$$
  सरल शब्दों में है. सबसे सरल अंश 3/y तीन अवधि के विस्तार के साथ है 3/7.
• एक अंश 4/y को इसके लालची विस्तार में चार शब्दों की आवश्यकता होती है यदि और केवल यदि y ≡ 1 or 17 (mod 24), तब अंश के लिए −y mod xशेष भिन्न का 3 है और हर है 1 (mod 6). सबसे सरल अंश 4/y चार अवधि के विस्तार के साथ है 4/17. एर्दो-स्ट्रॉस अनुमान बताता है कि सभी भिन्न 4/y तीन या उससे कम पदों के साथ विस्तार है, लेकिन कब y ≡ 1 or 17 (mod 24) ऐसे विस्तारों को लालची एल्गोरिदम के अलावा अन्य तरीकों से पाया जाना चाहिए 17 (mod 24) मामला सर्वांगसमता संबंध द्वारा कवर किया जा रहा है 2 (mod 3).

अधिक सामान्यतः भिन्नों का क्रम x/y जिसमें x-शब्द लालची विस्तार है और जिसमें प्रत्येक x के लिए सबसे छोटा संभव भाजक y है

$1,{\frac {2}{3}},{\frac {3}{7}},{\frac {4}{17}},{\frac {5}{31}},{\frac {6}{109}},{\frac {7}{253}},{\frac {8}{97}},{\frac {9}{271}},\dots$ (sequence A048860 in the OEIS).

बहुपद मूलों का सन्निकटन

Stratemeyer (1930) और Salzer (1947) लालची विधि के आधार पर एक सटीक जड़-खोज एल्गोरिथ्म खोजने की विधि का वर्णन करें। उनका एल्गोरिदम जड़ के लालची विस्तार की गणना करता है; इस विस्तार के प्रत्येक चरण में यह एक सहायक बहुपद बनाए रखता है जिसके मूल में विस्तारित होने वाला शेष अंश होता है। बहुपद समीकरण के दो समाधानों में से एक, सुनहरे अनुपात के लालची विस्तार को खोजने के लिए इस विधि को लागू करने के उदाहरण पर विचार करें P₀(x) = x² − x − 1 = 0. स्ट्रेटमेयर और साल्ज़र का एल्गोरिदम निम्नलिखित चरणों का क्रम निष्पादित करता है:

1. तब से P₀(x) < 0 x = 1 के लिए, और P₀(x) > 0 सभी के लिए x ≥ 2, P का मूल होना चाहिए₀(x) 1 और 2 के बीच। यानी स्वर्णिम अनुपात के लालची विस्तार का पहला पद है 1/1. यदि एक्स₁ लालची विस्तार के पहले चरण के बाद शेष अंश है, यह समीकरण को संतुष्ट करता है P₀(x₁ + 1) = 0, जिसे इस प्रकार विस्तारित किया जा सकता है P₁(x₁) = x²
   ₁ + x₁ − 1 = 0.
2. तब से P₁(x) < 0 x= के लिए1/2, और P₁(x) > 0 सभी के लिए x > 1, पी की जड़₁ बीच मे स्थित 1/2 और 1, और इसके लालची विस्तार में पहला पद (स्वर्णिम अनुपात के लिए लालची विस्तार में दूसरा पद) है 1/2. यदि एक्स₂ लालची विस्तार के इस चरण के बाद शेष अंश है, यह समीकरण को संतुष्ट करता है P₁(x₂ + 1/2) = 0, जिसे इस प्रकार विस्तारित किया जा सकता है P₂(x₂) = 4x²
   ₂ + 8x₂ − 1 = 0.
3. तब से P₂(x) < 0 x= के लिए1/9, और P₂(x) > 0 सभी के लिए x > 1/8, लालची विस्तार में अगला पद है 1/9. यदि एक्स₃ लालची विस्तार के इस चरण के बाद शेष अंश है, यह समीकरण को संतुष्ट करता है P₂(x₃ + 1/9) = 0, जिसे पूर्णांक गुणांक वाले बहुपद समीकरण के रूप में फिर से विस्तारित किया जा सकता है, P₃(x₃) = 324x²
   ₃ + 720x₃ − 5 = 0.

इस सन्निकटन प्रक्रिया को जारी रखने से अंततः सुनहरे अनुपात का लालची विस्तार उत्पन्न होता है,

$\varphi ={\frac {1}{1}}+{\frac {1}{2}}+{\frac {1}{9}}+{\frac {1}{145}}+{\frac {1}{37986}}+\cdots$ (sequence A117116 in the OEIS).

अन्य पूर्णांक अनुक्रम

छोटे अंशों और हर वाले सभी भिन्नों के लिए लालची विस्तार की लंबाई, न्यूनतम हर और अधिकतम हर अनुक्रम के रूप में पूर्णांक अनुक्रमों के ऑन-लाइन विश्वकोश में पाया जा सकता है। OEIS: A050205, OEIS: A050206, और OEIS: A050210, क्रमश। इसके अलावा, किसी भी अपरिमेय संख्या का लालची विस्तार पूर्णांकों के अनंत बढ़ते अनुक्रम की ओर जाता है, और OEIS में कई प्रसिद्ध स्थिरांक के विस्तार शामिल हैं। कुछ OEIS में अतिरिक्त प्रविष्टियाँ, हालांकि लालची एल्गोरिदम द्वारा निर्मित होने के रूप में लेबल नहीं की गई हैं, फिर भी वे एक ही प्रकार की प्रतीत होती हैं।

संबंधित विस्तार

सामान्य तौर पर, यदि कोई मिस्र के अंश का विस्तार चाहता है जिसमें हर किसी तरह से बाधित हो, तो एक लालची एल्गोरिदम को परिभाषित करना संभव है जिसमें प्रत्येक चरण पर विस्तार का चयन किया जाता है

$${\frac {x}{y}}={\frac {1}{d}}+{\frac {xd-y}{yd}},$$

कहाँ $d$ बाधाओं को संतुष्ट करने वाले सभी संभावित मूल्यों में से, जितना संभव हो उतना छोटा चुना जाता है $xd>y$ और ऐसा कि $d$ पहले से चुने गए सभी विभाजकों से अलग है। इस तरह से परिभाषित तरीकों के उदाहरणों में एंगेल विस्तार शामिल है, जिसमें प्रत्येक क्रमिक हर पिछले एक का एक गुणक होना चाहिए, और विषम लालची विस्तार, जिसमें सभी हर विषम संख्या होने के लिए बाध्य हैं।

हालाँकि, यह निर्धारित करना मुश्किल हो सकता है कि क्या इस प्रकार का एल्गोरिदम हमेशा एक सीमित विस्तार खोजने में सफल हो सकता है। विशेष रूप से, यह अज्ञात है कि क्या विषम लालची विस्तार सभी अंशों के लिए एक सीमित विस्तार के साथ समाप्त होता है $x/y$ जिसके लिए $y$ अजीब है, हालाँकि गैर-लालची तरीकों से इन भिन्नों के लिए सीमित विषम विस्तार खोजना संभव है।

संदर्भ

• Cahen, E. (1891), "Note sur un développement des quantités numériques, qui presente quelque analogie avec celui en fractions continues", Nouvelles Annales des Mathématiques, Ser. 3, 10: 508–514.
• Curtiss, D. R. (1922), "On Kellogg's diophantine problem", American Mathematical Monthly, 29 (10): 380–387, doi:10.2307/2299023, JSTOR 2299023.
• Freitag, H. T.; Phillips, G. M. (1999), "Sylvester's algorithm and Fibonacci numbers", Applications of Fibonacci numbers, Vol. 8 (Rochester, NY, 1998), Dordrecht: Kluwer Acad. Publ., pp. 155–163, MR 1737669.
• Lambert, J. H. (1770), Beyträge zum Gebrauche der Mathematik und deren Anwendung, Berlin: Zweyter Theil, pp. 99–104.
• Mays, Michael (1987), "A worst case of the Fibonacci–Sylvester expansion", Journal of Combinatorial Mathematics and Combinatorial Computing, 1: 141–148, MR 0888838.
• Salzer, H. E. (1947), "The approximation of numbers as sums of reciprocals", American Mathematical Monthly, 54 (3): 135–142, doi:10.2307/2305906, JSTOR 2305906, MR 0020339.
• Salzer, H. E. (1948), "Further remarks on the approximation of numbers as sums of reciprocals", American Mathematical Monthly, 55 (6): 350–356, doi:10.2307/2304960, JSTOR 2304960, MR 0025512.
• Sigler, Laurence E. (trans.) (2002), Fibonacci's Liber Abaci, Springer-Verlag, ISBN 0-387-95419-8.
• Soundararajan, K. (2005), Approximating 1 from below using n Egyptian fractions, arXiv:math.CA/0502247.
• Spiess, O. (1907), "Über eine Klasse unendlicher Reihen", Archiv der Mathematik und Physik, Third Series, 12: 124–134.
• Stong, R. E. (1983), "Pseudofree actions and the greedy algorithm", Mathematische Annalen, 265 (4): 501–512, doi:10.1007/BF01455950, MR 0721884, S2CID 120347233.
• Stratemeyer, G. (1930), "Stammbruchentwickelungen für die Quadratwurzel aus einer rationalen Zahl", Mathematische Zeitschrift, 31: 767–768, doi:10.1007/BF01246446, S2CID 120956180.
• Sylvester, J. J. (1880), "On a point in the theory of vulgar fractions", American Journal of Mathematics, 3 (4): 332–335, doi:10.2307/2369261, JSTOR 2369261.
• Wagon, S. (1991), Mathematica in Action, W. H. Freeman, pp. 271–277.