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

{{Short description|Simple method for finding Egyptian fractions.}}
गणित में, '''मिस्र के भिन्नों के लिए ग्रीडी एल्गोरिदम''' एक ग्रीडी एल्गोरिदम है, जिसे पहली बार फिबोनाची द्वारा मिस्र के भिन्नों में तर्कसंगत संख्याओं को बदलने के लिए वर्णित किया गया है। मिस्र का भिन्न भिन्न इकाई अंशों के योग के रूप में एक अपरिवर्तनीय अंश का प्रतिनिधित्व करता है, जैसे कि {{nowrap|1={{sfrac|5|6}} = {{sfrac|1|2}} + {{sfrac|1|3}}}}। जैसा कि नाम से संकेत मिलता है, इन अभ्यावेदनों का उपयोग प्राचीन मिस्र में बहुत पहले से किया जाता रहा है, लेकिन इस तरह के विस्तार के निर्माण के लिए पहली प्रकाशित व्यवस्थित विधि का वर्णन 1202 में [[पीसा के लियोनार्डो]] के लिबर अबासी (फिबोनाची) में किया गया था।{{sfn|Sigler|2002}} इसे ग्रीडी एल्गोरिदम कहा जाता है क्योंकि प्रत्येक चरण में एल्गोरिदम ग्रीड से सबसे बड़ा संभावित इकाई अंश चुनता है जिसका उपयोग शेष अंश के किसी भी प्रतिनिधित्व में किया जा सकता है।

फिबोनाची वास्तव में मिस्र के अंश प्रतिनिधित्व के निर्माण के लिए कई अलग-अलग तरीकों को सूचीबद्ध करता है।<ref>{{harvnb|Sigler|2002}}, chapter II.7</ref> जब कई सरल तरीके विफल हो जाते हैं तो वह उन स्थितियों के लिए अंतिम उपाय के रूप में ग्रीडी पद्धति को शामिल करता है; इन तरीकों की अधिक विस्तृत सूची के लिए मिस्र का अंश देखें। जैसा कि साल्ज़र (1948) ने विवरण दिया है, आधुनिक गणितज्ञों द्वारा अपरिमेय संख्याओं के सन्निकटन के लिए ग्रीडी पद्धति और उसके विस्तार को कई बार फिर से खोजा गया है, जे जे सिल्वेस्टर (1880) द्वारा सबसे प्रारंभिक और सबसे उल्लेखनीय<ref>See for instance {{harvtxt|Cahen|1891}} and {{harvtxt|Spiess|1907}}.</ref> एक बारीकी से संबंधित विस्तार विधि जो योग में कुछ इकाई अंशों को ऋणात्मक होने की अनुमति देकर प्रत्येक चरण पर करीब अनुमान उत्पन्न करती है, लैंबर्ट (1770) की है।

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

==एल्गोरिदम और उदाहरण==
फिबोनाची का एल्गोरिदम अंश का विस्तार करता है <math>x/y</math> बार-बार प्रतिस्थापन करके, प्रतिनिधित्व किया जाना
<math display=block>\frac{x}{y}=\frac{1}{\left\lceil \frac y x \right\rceil}+\frac{(-y)\bmod x}{y\left\lceil \frac y x \right\rceil}</math>
(आवश्यकतानुसार इस प्रतिस्थापन में दूसरे पद को सरल बनाना)। उदाहरण के लिए:
<math display=block>\frac{7}{15}=\frac{1}{3}+\frac{2}{15}=\frac{1}{3}+\frac{1}{8}+\frac{1}{120}.</math>
इस विस्तार में, पहली इकाई भिन्न का हर 3 पूर्णांकन का परिणाम है {{sfrac|15|7}} अगले बड़े पूर्णांक तक, और शेष भिन्न तक {{sfrac|2|15}}सरलीकरण का परिणाम है {{sfrac|−15 mod 7|15 × 3}} = {{sfrac|6|45}}. दूसरी इकाई भिन्न का हर, 8, पूर्णांकन का परिणाम है {{sfrac|15|2}} अगले बड़े पूर्णांक तक, और शेष भिन्न तक {{sfrac|1|120}} वही है जो बचा हुआ है {{sfrac|7|15}}दोनों को घटाने के बाद {{sfrac|1|3}} और {{sfrac|1|8}}.

चूंकि प्रत्येक विस्तार चरण विस्तारित किए जाने वाले शेष अंश के अंश को कम कर देता है, यह विधि हमेशा एक सीमित विस्तार के साथ समाप्त होती है; हालाँकि, प्राचीन मिस्र के विस्तार या अधिक आधुनिक तरीकों की तुलना में, यह विधि बड़े हर के साथ काफी लंबे विस्तार उत्पन्न कर सकती है। उदाहरण के लिए, यह विधि विस्तारित होती है
<math display=block>\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},</math>
जबकि अन्य तरीकों से काफी बेहतर विस्तार होता है
<math display=block>\frac{5}{121}=\frac{1}{33}+\frac{1}{121}+\frac{1}{363}.</math>
{{harvtxt|Wagon|1991}} इससे भी अधिक बुरे व्यवहार वाला उदाहरण सुझाता है, {{sfrac|31|311}}. ग्रीडी विधि दस पदों के साथ विस्तार की ओर ले जाती है, जिनमें से अंतिम के हर में 500 से अधिक अंक होते हैं; हालाँकि, {{sfrac|31|311}} का गैर-ग्रीडी प्रतिनिधित्व बहुत छोटा है, {{nowrap|{{sfrac|1|12}} + {{sfrac|1|63}} + {{sfrac|1|2799}} + {{sfrac|1|8708}}}}.

==सिल्वेस्टर का अनुक्रम और निकटतम सन्निकटन==
सिल्वेस्टर का अनुक्रम 2, 3, 7, 43, 1807, ... ({{OEIS2C|A000058}}) को संख्या 1 के लिए इस प्रकार के अनंत ग्रीडी विस्तार द्वारा उत्पन्न के रूप में देखा जा सकता है, जहां प्रत्येक चरण में हम हर को चुनते हैं {{nowrap|⌊ {{sfrac|''y''|''x''}} ⌋ + 1}} के बजाय {{nowrap|⌈ {{sfrac|''y''|''x''}} ⌉}}. इस अनुक्रम को k पदों में छोटा करना और संगत मिस्री अंश बनाना, उदाहरणार्थ (k=4 के लिए)
<math display=block>\frac12+\frac13+\frac17+\frac1{43}=\frac{1805}{1806}</math>
किसी भी k-टर्म मिस्री अंश द्वारा 1 के निकटतम संभावित कम अनुमान का परिणाम होता है।<ref>{{harvnb|Curtiss|1922}}; {{harvnb|Soundararajan|2005}}</ref> उदाहरण के लिए, खुले अंतराल में किसी संख्या के लिए कोई मिस्री अंश ({{sfrac|1805|1806}}, 1) कम से कम पांच शब्दों की आवश्यकता है। {{harvtxt|Curtiss|1922}} एक पूर्ण संख्या के विभाजकों की संख्या को कम करने में इन निकटतम-अनुमान परिणामों के अनुप्रयोग का वर्णन करता है, जबकि {{harvtxt|Stong|1983}} [[समूह सिद्धांत]] में अनुप्रयोगों का वर्णन करता है।

==अधिकतम-लंबाई विस्तार और सर्वांगसमता स्थितियाँ==
कोई भी अंश {{sfrac|''x''|''y''}} को अपने ग्रीडी विस्तार में अधिकतम x पदों की आवश्यकता होती है। {{harvtxt|Mays|1987}} और {{harvtxt|Freitag|Phillips|1999}} उन परिस्थितियों की जांच करें जिनके तहत ग्रीडी पद्धति का विस्तार उत्पन्न होता है {{sfrac|''x''|''y''}} बिल्कुल x पदों के साथ; इन्हें y पर सर्वांगसमता स्थितियों के संदर्भ में वर्णित किया जा सकता है।

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

अधिक सामान्यतः भिन्नों का क्रम {{sfrac|''x''|''y''}} जिसमें x-शब्द ग्रीडी विस्तार है और जिसमें प्रत्येक x के लिए सबसे छोटा संभव भाजक y है
{{bi|left=1.6|<math>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</math> {{OEIS|id=A048860}}.}}

==बहुपद मूलों का सन्निकटन==
{{harvtxt|Stratemeyer|1930}} और {{harvtxt|Salzer|1947}} ग्रीडी विधि के आधार पर एक सटीक [[जड़-खोज एल्गोरिथ्म|जड़-खोज एल्गोरिदम]] खोजने की विधि का वर्णन करें। उनका एल्गोरिदम जड़ के ग्रीडी विस्तार की गणना करता है; इस विस्तार के प्रत्येक चरण में यह एक सहायक बहुपद बनाए रखता है जिसके मूल में विस्तारित होने वाला शेष अंश होता है। बहुपद समीकरण के दो समाधानों में से एक, सुनहरे अनुपात के ग्रीडी विस्तार को खोजने के लिए इस विधि को लागू करने के उदाहरण पर विचार करें {{nowrap|1=''P''<sub>0</sub>(''x'') = ''x''<sup>2</sup> − ''x'' − 1 = 0}}. स्ट्रेटमेयर और साल्ज़र का एल्गोरिदम निम्नलिखित चरणों का क्रम निष्पादित करता है:

#तब से {{nowrap|''P''<sub>0</sub>(''x'') < 0}} x = 1 के लिए, और {{nowrap|''P''<sub>0</sub>(''x'') > 0}} सभी के लिए {{nowrap|''x'' ≥ 2}}, P का मूल होना चाहिए<sub>0</sub>(x) 1 और 2 के बीच। यानी स्वर्णिम अनुपात के ग्रीडी विस्तार का पहला पद है {{sfrac|1|1}}. यदि एक्स<sub>1</sub> ग्रीडी विस्तार के पहले चरण के बाद शेष अंश है, यह समीकरण को संतुष्ट करता है {{nowrap|1=''P''<sub>0</sub>(''x''<sub>1</sub> + 1) = 0}}, जिसे इस प्रकार विस्तारित किया जा सकता है {{nowrap|1=''P''<sub>1</sub>(''x''<sub>1</sub>) = ''x''{{su|b=1|p=2}} + ''x''<sub>1</sub> − 1 = 0}}.
#तब से {{nowrap|''P''<sub>1</sub>(''x'') < 0}} x= के लिए{{sfrac|1|2}}, और {{nowrap|''P''<sub>1</sub>(''x'') > 0}} सभी के लिए {{nowrap|''x'' > 1}}, पी की जड़<sub>1</sub> बीच मे स्थित {{sfrac|1|2}} और 1, और इसके ग्रीडी विस्तार में पहला पद (स्वर्णिम अनुपात के लिए ग्रीडी विस्तार में दूसरा पद) है {{sfrac|1|2}}. यदि एक्स<sub>2</sub> ग्रीडी विस्तार के इस चरण के बाद शेष अंश है, यह समीकरण को संतुष्ट करता है {{nowrap|1=''P''<sub>1</sub>(''x''<sub>2</sub> + {{sfrac|1|2}}) = 0}}, जिसे इस प्रकार विस्तारित किया जा सकता है {{nowrap|1=''P''<sub>2</sub>(''x''<sub>2</sub>) = 4''x''{{su|b=2|p=2}} + 8''x''<sub>2</sub> − 1 = 0}}.
#तब से {{nowrap|''P''<sub>2</sub>(''x'') < 0}} x= के लिए{{sfrac|1|9}}, और {{nowrap|''P''<sub>2</sub>(''x'') > 0}} सभी के लिए {{nowrap|''x'' > {{sfrac|1|8}}}}, ग्रीडी विस्तार में अगला पद है {{sfrac|1|9}}. यदि एक्स<sub>3</sub> ग्रीडी विस्तार के इस चरण के बाद शेष अंश है, यह समीकरण को संतुष्ट करता है {{nowrap|1=''P''<sub>2</sub>(''x''<sub>3</sub> + {{sfrac|1|9}}) = 0}}, जिसे पूर्णांक गुणांक वाले बहुपद समीकरण के रूप में फिर से विस्तारित किया जा सकता है, {{nowrap|1=''P''<sub>3</sub>(''x''<sub>3</sub>) = 324''x''{{su|b=3|p=2}} + 720''x''<sub>3</sub> − 5 = 0}}.

इस सन्निकटन प्रक्रिया को जारी रखने से अंततः सुनहरे अनुपात का ग्रीडी विस्तार उत्पन्न होता है,
{{bi|left=1.6|<math>\varphi = \frac11+\frac12+\frac19+\frac1{145}+\frac1{37986}+\cdots</math> {{OEIS|id=A117116}}.}}

==अन्य पूर्णांक अनुक्रम==
छोटे अंशों और हर वाले सभी भिन्नों के लिए ग्रीडी विस्तार की लंबाई, न्यूनतम हर और अधिकतम हर अनुक्रम के रूप में पूर्णांक अनुक्रमों के ऑन-लाइन विश्वकोश में पाया जा सकता है। {{OEIS2C|A050205}}, {{OEIS2C|A050206}}, और {{OEIS2C|A050210}}, क्रमश। इसके अलावा, किसी भी [[अपरिमेय संख्या]] का ग्रीडी विस्तार पूर्णांकों के अनंत बढ़ते अनुक्रम की ओर जाता है, और OEIS में [http://oeis.org/search?q=greedy-Egyptian-fraction-expansion कई प्रसिद्ध स्थिरांक के विस्तार] शामिल हैं। कुछ [http://oeis.org/search?q=Egyptian-fraction-for OEIS में अतिरिक्त प्रविष्टियाँ], हालांकि ग्रीडी एल्गोरिदम द्वारा निर्मित होने के रूप में लेबल नहीं की गई हैं, फिर भी वे एक ही प्रकार की प्रतीत होती हैं।

==संबंधित विस्तार==
सामान्य तौर पर, यदि कोई मिस्र के अंश का विस्तार चाहता है जिसमें हर किसी तरह से बाधित हो, तो एक ग्रीडी एल्गोरिदम को परिभाषित करना संभव है जिसमें प्रत्येक चरण पर विस्तार का चयन किया जाता है
<math display=block>\frac{x}{y}=\frac{1}{d}+\frac{xd-y}{yd},</math>
कहाँ <math>d</math> बाधाओं को संतुष्ट करने वाले सभी संभावित मूल्यों में से, जितना संभव हो उतना छोटा चुना जाता है <math>xd > y</math> और ऐसा कि <math>d</math> पहले से चुने गए सभी विभाजकों से अलग है। इस तरह से परिभाषित तरीकों के उदाहरणों में एंगेल विस्तार शामिल है, जिसमें प्रत्येक क्रमिक हर पिछले एक का एक गुणक होना चाहिए, और विषम ग्रीडी विस्तार, जिसमें सभी हर विषम संख्या होने के लिए बाध्य हैं।

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

==टिप्पणियाँ==
{{reflist}}


== संदर्भ ==
{{refbegin|colwidth=30em}}
*{{citation
 | last = Cahen | first = E.
 | journal = Nouvelles Annales des Mathématiques | series = Ser. 3
 | pages = 508–514
 | title = Note sur un développement des quantités numériques, qui presente quelque analogie avec celui en fractions continues
 | volume = 10
 | year = 1891}}.
*{{citation
 | last = Curtiss | first = D. R. | authorlink = David Raymond Curtiss
 | doi = 10.2307/2299023
 | issue = 10
 | journal = [[American Mathematical Monthly]]
 | jstor = 2299023
 | pages = 380–387
 | title = On Kellogg's diophantine problem
 | volume = 29
 | year = 1922}}.
*{{citation
 | last1 = Freitag | first1 = H. T. | author1-link = Herta Freitag
 | last2 = Phillips | first2 = G. M.
 | contribution = Sylvester's algorithm and Fibonacci numbers
 | location = Dordrecht
 | mr = 1737669
 | pages = 155–163
 | publisher = Kluwer Acad. Publ.
 | title = Applications of Fibonacci numbers, Vol. 8 (Rochester, NY, 1998)
 | year = 1999}}.
*{{citation
 | last = Lambert | first = J. H. | author-link = Johann Heinrich Lambert
 | location = Berlin
 | pages = 99–104
 | publisher = Zweyter Theil
 | title = Beyträge zum Gebrauche der Mathematik und deren Anwendung
 | year = 1770}}.
*{{citation
 | last = Mays | first = Michael
 | journal = Journal of Combinatorial Mathematics and Combinatorial Computing
 | mr = 0888838
 | pages = 141–148
 | title = A worst case of the Fibonacci–Sylvester expansion
 | volume = 1
 | year = 1987}}.
*{{citation
 | last = Salzer | first = H. E.
 | doi = 10.2307/2305906
 | issue = 3
 | journal = [[American Mathematical Monthly]]
 | jstor = 2305906
 | mr = 0020339
 | pages = 135–142
 | title = The approximation of numbers as sums of reciprocals
 | volume = 54
 | year = 1947}}.
*{{citation
 | last = Salzer | first = H. E.
 | doi = 10.2307/2304960
 | issue = 6
 | journal = [[American Mathematical Monthly]]
 | jstor = 2304960
 | mr = 0025512
 | pages = 350–356
 | title = Further remarks on the approximation of numbers as sums of reciprocals
 | volume = 55
 | year = 1948}}.
*{{citation
 | last = Sigler | first = Laurence E. (trans.)
 | isbn = 0-387-95419-8
 | publisher = Springer-Verlag
 | title = Fibonacci's Liber Abaci
 | year = 2002}}.
*{{citation
 | last = Soundararajan | first = K.
 | arxiv = math.CA/0502247
 | title = Approximating 1 from below using ''n'' Egyptian fractions
 | year = 2005}}.
*{{citation
 | last = Spiess | first = O.
 | journal = Archiv der Mathematik und Physik |series=Third Series
 | pages = 124–134
 | title = Über eine Klasse unendlicher Reihen
 | volume = 12
 | year = 1907}}.
*{{citation
 | last = Stong | first = R. E. | authorlink = Robert Evert Stong
 | doi = 10.1007/BF01455950
 | issue = 4
 | journal = Mathematische Annalen
 | mr = 0721884
 | pages = 501–512
 | title = Pseudofree actions and the greedy algorithm
 | volume = 265
 | year = 1983| s2cid = 120347233 }}.
*{{citation
 | last = Stratemeyer | first = G.
 | doi = 10.1007/BF01246446
 | journal = Mathematische Zeitschrift
 | pages = 767–768
 | title = Stammbruchentwickelungen für die Quadratwurzel aus einer rationalen Zahl
 | volume = 31
 | year = 1930| s2cid = 120956180
 }}.
*{{citation
 | last = Sylvester | first = J. J. | author-link = J. J. Sylvester
 | doi = 10.2307/2369261
 | issue = 4
 | journal = [[American Journal of Mathematics]]
 | jstor = 2369261
 | pages = 332–335
 | title = On a point in the theory of vulgar fractions
 | volume = 3
 | year = 1880}}.
*{{citation
 | last = Wagon | first = S. | authorlink = Stan Wagon
 | pages = 271–277
 | publisher = W. H. Freeman
 | title = Mathematica in Action
 | year = 1991}}.
{{refend}}

{{Fibonacci}}
[[Category: मिस्र के अंश]] [[Category: लालची एल्गोरिदम]] 



[[Category: Machine Translated Page]]
[[Category:Created On 26/07/2023]]