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

गणित में, मिस्र के भिन्नों के लिए ग्रीडी एल्गोरिदम एक ग्रीडी एल्गोरिदम है, जिसे पहली बार फिबोनाची द्वारा मिस्र के भिन्नों में तर्कसंगत संख्याओं को बदलने के लिए वर्णित किया गया है। मिस्र का भिन्न भिन्न इकाई अंशों के योग के रूप में अपरिवर्तनीय अंश का प्रतिनिधित्व करता है, जैसे कि 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}}.$$

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

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

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

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

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

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

किसी भी अंश x/y को अपने ग्रीडी विस्तार में अधिकतम x शब्दों की आवश्यकता होती है। मेज़ (1987) और फ़्रीटैग एंड फिलिप्स (1999) उन स्थितियों की जांच करते हैं जिनके तहत ग्रीडी विधि बिल्कुल x शर्तों के साथ x/y का विस्तार उत्पन्न करती है; इनका वर्णन 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).

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

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

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