Odd Greedy Descompunere

Expansiunea lacomă impară este o metodă de construire a fracțiilor egiptene în care toți numitorii sunt impari.

Dacă un număr rațional este suma fracțiilor alicote impare : $X y$

{\frac {x}{y}}=\sum {\frac {1}{2a_{i}+1}}

atunci numărul trebuie să fie impar. Dimpotrivă, se știe că în cazul unui număr impar, orice fracție a formei are o expansiune cu numitori impari, în care toți numitorii fracțiilor sunt diferiți. De exemplu, o astfel de descompunere poate fi găsită prin înlocuirea cu , unde este un număr de forma pentru suficient de mare , iar apoi reprezentând ca sumă de divizori [1] . $y$ $y$ $X y$ $X y$ $Ax/Ay$ $A$ $35\times 3^{i)$ $i$ $Topor$ $Ay$

Cu toate acestea, există un algoritm mai simplu lacom care găsește cu succes fracții egiptene cu numitori impari pentru toate numerele (cu impar ) pe care este testat: să fie cel mai mic număr impar nu mai puțin de , fracția este inclusă în expansiune și procesul continuă pentru fracția reziduală . Această metodă se numește algoritm lacom impar, iar descompunerea rezultată se numește descompunere greedy impar. $X y$ $y$ $u$ $y/x$ $1/u$ $x/y-1/u$

Întrebarea dacă procesul de extindere se va încheia într-un număr finit de pași pentru orice număr impar [2] a rămas deschisă din 2006 . $X y$ $y$

Aplicarea algoritmului unei fracții cu numitor par dă o expansiune infinită. De exemplu, secvența Sylvester poate fi văzută ca rezultatul unui algoritm de fracție neplăcută . $1/2$

Exemplu

Fie x / y = 4/23.

23/4 = 5 ¾, următorul număr impar mai mare este 7. Astfel, la primul pas obținem expansiunea:

4/23 = 1/7 + 5/161.

161/5 = 32 1/5, următorul număr impar mai mare este 33. Astfel, la pasul următor, obținem expansiunea:

4/23 = 1/7 + 1/33 + 4/5313.

5313/4 = 1328 1/4, următorul număr impar mai mare este 1329. Astfel, la al treilea pas obținem expansiunea:

4/23 = 1/7 + 1/33 + 1/1329 + 1/2353659.

Întrucât la a treia etapă din numărătorul unității de fracție reziduală se obține, procesul se oprește și, ca urmare, se obține o expansiune finită.

Fracții cu expansiuni lungi

Algoritmul greedy impar poate genera descompunere mai scurtă decât descompunerea greedy obișnuită și cu numitori mai mici [3] . De exemplu,

{\frac {8}{77}}={\frac {1}{10}}+{\frac {1}{257}}+{\frac {1}{197890}}={\frac {1}{11}}+{\frac {1}{77}},

unde descompunerea din stânga este obținută printr-un algoritm greedy, iar descompunerea din dreapta este obținută printr-un algoritm greedy impar. Cu toate acestea, de regulă, rezultatul descompunerii de către un algoritm ciudat lacom este mai lung și are numitori mari. De exemplu [4] , expansiunea lacomă impară a 3/179 dă 19 termeni, dintre care cel mai mare este aproximativ egal cu 1,415×10 439491 . Interesant este că numărătorii fracțiilor de expansiune formează o succesiune de numere întregi:

3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 1.

Cazuri similare apar cu alte numere, cum ar fi 5/5809 (exemplu găsit independent de KS Brown și David Bailey ), caz în care extinderea are 31 de termeni. Deși numitorii acestei expansiuni sunt dificil de calculat din cauza mărimii lor, succesiunea numărătorilor poate fi găsită relativ eficient folosind aritmetica modulară . În 1999 [5] , sunt descrise câteva exemple suplimentare de acest tip și sunt date metode pentru găsirea fracțiilor care dau expansiuni arbitrar lungi.

Literatură

R. Breusch. Un caz special de fracții egiptene, soluție la problema avansată 4512 // American Mathematical Monthly . - 1954. - T. 61 . - S. 200-201 .
Richard K Guy. Probleme nerezolvate în teoria numerelor. - 1981. - S. 88. - ISBN 0-387-90593-6 .
Richard K Guy. Nimic nou în teoria numerelor? // American Mathematical Monthly . - 1998. - T. 105 , nr. 10 . - S. 951-954 . - doi : 10.2307/2589289 . — .
Victor Klee, Stan Wagon. Probleme nerezolvate în geometria elementară și teoria numerelor. — 1991.
Richard Nowakowski. Probleme nerezolvate, 1969-1999 // American Mathematical Monthly . - 1999. - T. 106 , nr. 10 . - S. 959-962 . - doi : 10.2307/2589753 . — .
BM Stewart. Sume ale divizorilor distincti // American Journal of Mathematics . - 1954. - T. 76 , nr. 4 . - S. 779-785 . - doi : 10.2307/2372651 . — .
Stan Wagon. Mathematica în acțiune . - W. H. Freeman, 1991. - S. 275 -277. — ISBN 0-7167-2202-X .
MathPages - Odd-Greedy Unit Fraction Expansions , KS Brown