Udda girig nedbrytning

Udda girig expansion är en metod för att konstruera egyptiska bråk där alla nämnare är udda.

Om ett rationellt tal är summan av udda delmängder : $x/y$

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

då måste siffran vara udda. Omvänt är det känt att i fallet med ett udda tal har varje bråkdel av formen en expansion med udda nämnare, där alla bråkens nämnare är olika. Till exempel kan en sådan nedbrytning hittas genom att ersätta med , där är ett antal av formen för tillräckligt stor , och sedan representera som en summa av divisorer [1] . $y$ $y$ $x/y$ $x/y$ $Axe/Ay$ $A$ ${\displaystyle 35\times 3^{i))$ $i$ $Yxa$ $Ay$

Det finns dock en enklare girig algoritm som framgångsrikt hittar egyptiska bråk med udda nämnare för alla tal (med udda ) som den testas på: låt vara det minsta udda talet inte mindre än , bråket ingår i expansionen och processen fortsätter för restfraktionen . Denna metod kallas den udda giriga algoritmen, och den resulterande nedbrytningen kallas den udda giriga nedbrytningen. $x/y$ $y$ $u$ $y/x$ $1/u$ $x/y-1/u$

Frågan om huruvida expansionsprocessen kommer att sluta i ett ändligt antal steg för något udda nummer [2] förblev öppen från och med 2006 . $x/y$ $y$

Att tillämpa algoritmen på ett bråk med en jämn nämnare ger en oändlig expansion. Till exempel kan Sylvester-sekvensen ses som resultatet av en udda girig bråkalgoritm . $1/2$

Exempel

Låt x / y = 4/23.

23/4 = 5 ¾, nästa större udda tal är 7. I det första steget får vi alltså nedbrytningen:

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

161/5 = 32 1/5, nästa större udda tal är 33. I nästa steg får vi alltså expansionen:

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

5313/4 = 1328 1/4, nästa större udda tal är 1329. I det tredje steget får vi alltså nedbrytningen:

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

Eftersom vid det tredje steget i täljaren av restfraktionsenheten erhålls, stannar processen och som ett resultat erhålls en ändlig expansion.

Bråk med långa expansioner

Den udda giriga algoritmen kan generera nedbrytningar som är kortare än den vanliga giriga nedbrytningen och med mindre nämnare [3] . Till exempel,

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

där nedbrytningen till vänster erhålls av en girig algoritm, och nedbrytningen till höger erhålls av en udda girig algoritm. Men som regel är resultatet av nedbrytning med en udda girig algoritm längre och har stora nämnare. Till exempel [4] , den udda giriga expansionen på 3/179 ger 19 termer, varav den största är ungefär lika med 1,415×10 439491 . Intressant nog bildar täljarna av expansionsfraktionerna en sekvens av heltal:

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

Liknande fall förekommer med andra nummer som 5/5809 (exempel hittat oberoende av KS Brown och David Bailey ) i vilket fall expansionen har 31 termer. Även om nämnarna för denna expansion är svåra att beräkna på grund av deras stora storlek, kan täljarsekvensen hittas relativt effektivt med modulära aritmetik . 1999 [5] beskrivs ytterligare några exempel av denna typ och metoder ges för att hitta fraktioner som ger godtyckligt långa expansioner.

Litteratur

R. Breusch. Ett specialfall av egyptiska bråk, lösning på avancerat problem 4512 // American Mathematical Monthly . - 1954. - T. 61 . - S. 200-201 .
Richard K Guy. Olösta problem i talteorin. - 1981. - S. 88. - ISBN 0-387-90593-6 .
Richard K Guy. Inget nytt i talteorin? // American Mathematical Monthly . - 1998. - T. 105 , nr. 10 . - S. 951-954 . - doi : 10.2307/2589289 . — .
Victor Klee, Stan Wagon. Olösta problem i elementär geometri och talteori. — 1991.
Richard Nowakowski. Olösta problem, 1969-1999 // American Mathematical Monthly . - 1999. - T. 106 , nummer. 10 . - S. 959-962 . - doi : 10.2307/2589753 . — .
BM Stewart. Summor av distinkta divisorer // American Journal of Mathematics . - 1954. - T. 76 , nr. 4 . - S. 779-785 . - doi : 10.2307/2372651 . — .
Stan Wagon. Mathematica in Action . - W. H. Freeman, 1991. - S. 275 -277. — ISBN 0-7167-2202-X .
MathPages - Odd-Greedy Unit Fraction Expansions , KS Brown