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

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

फिबोनाची वास्तव में मिस्र के अंश प्रतिनिधित्व के निर्माण के लिए कई अलग-अलग तरीकों को सूचीबद्ध करता है। जब कई सरल तरीके विफल हो जाते हैं तो वह उन स्थितियों के लिए अंतिम उपाय के रूप में ग्रीडी पद्धति को शामिल करता है; इन तरीकों की अधिक विस्तृत सूची के लिए मिस्र का अंश देखें। जैसा कि साल्ज़र (1948) ने विवरण दिया है, आधुनिक गणितज्ञों द्वारा अपरिमेय संख्याओं के सन्निकटन के लिए ग्रीडी पद्धति और उसके विस्तार को कई बार फिर से खोजा गया है, जे जे सिल्वेस्टर (1880) द्वारा सबसे प्रारंभिक और सबसे उल्लेखनीय एक बारीकी से संबंधित विस्तार विधि जो योग में कुछ इकाई अंशों को ऋणात्मक होने की अनुमति देकर प्रत्येक चरण पर करीब अनुमान उत्पन्न करती है, लैंबर्ट (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 वह है जो 1/3 और 1/8 दोनों को घटाने के बाद 7/15 से बचता है। चूँकि प्रत्येक विस्तार चरण विस्तारित किए जाने वाले शेष भिन्न के अंश को कम कर देता है, यह विधि हमेशा एक सीमित विस्तार के साथ समाप्त होती है; हालाँकि, प्राचीन मिस्र के विस्तारों या अधिक आधुनिक तरीकों की तुलना में, यह विधि ऐसे विस्तार उत्पन्न कर सकती है जो बड़े हर के साथ काफी लंबे हैं। उदाहरण के लिए, इस पद्धति का विस्तार होता है।

$${\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.