Rosetta Code

Greedy algorithm for Egyptian fractions: Difference between revisions

Page Discussion

Greedy algorithm for Egyptian fractions (view source)

Revision as of 16:12, 12 December 2023

15,628 bytes added ,  5 months ago
Added link to numberphile video
m (syntax highlighting fixup automation)
(Added link to numberphile video)
 
(9 intermediate revisions by 5 users not shown)
Line 41:
;Also see:
*   Wolfram MathWorld™ entry: [http://mathworld.wolfram.com/EgyptianFraction.html Egyptian fraction]
*   Numberphile YouTube video: [https://youtu.be/aVUUbNbQkbQ Egyptian Fractions and the Greedy Algorithm]
<br><br>
 
Line 459 ⟶ 460:
{{libheader|Boost}}
The C++ standard library does not have a "big integer" type, so this solution uses the Boost library.
<syntaxhighlight lang="cpp">#include <iostreamboost/multiprecision/cpp_int.hpp>
#include <iostream>
#include <optional>
#include <vector>
#include <string>
#include <sstream>
#include <boost/multiprecision/cpp_int.hppstring>
#include <vector>
 
typedef boost::multiprecision::cpp_int integer;
 
struct fraction {
fraction(const integer& n, const integer& d) : numerator(n), denominator(d) {}
: numerator(n), denominator(d) {}
integer numerator;
integer denominator;
};
 
integer mod(const integer& x, const integer& y) { return ((x % y) + y) % y; }
return ((x % y) + y) % y;
}
 
size_t count_digits(const integer& i) {
Line 489:
os << i;
std::string s = os.str();
if (s.length() > max_digits) {
s.replace(max_digits =/ 2, s.substrlength(0,) - max_digits/2) +, "..." + s.substr(s.length()-max_digits/2);
}
return s;
}
Line 503 ⟶ 502:
integer x = f.numerator, y = f.denominator;
while (x > 0) {
integer z = (y + x - 1) / x;
result.emplace_back(1, z);
x = mod(-y, x);
Line 524 ⟶ 523:
integer x = f.numerator, y = f.denominator;
if (x > y) {
std::cout << "[" << x / y << "] ";
x = x % y;
}
Line 557 ⟶ 556:
}
}
std::cout
std::cout << "Proper fractions with most terms and largest denominator, limit = " << limit << ":\n\n";
<< "Proper fractions with most terms and largest denominator, limit = "
std::cout << "Most terms (" << max_terms << "): " << max_terms_fraction.value() << " = ";
<< limit << ":\n\n";
std::cout << "Most terms (" << max_terms
<< "): " << max_terms_fraction.value() << " = ";
print_egyptian(max_terms_result);
std::cout << "\nLargest denominator (" << count_digits(max_denominator_result.back().denominator)
<< " digits): " << max_denominator_fractioncount_digits(max_denominator_result.valueback() << " = ";.denominator)
<< " digits): " << max_denominator_fraction.value() << " = ";
print_egyptian(max_denominator_result);
}
Line 775 ⟶ 778:
</pre>
 
=={{header|F_Sharp|F#}}==
<syntaxhighlight lang="fsharp">
// Greedy algorithm for Egyptian fractions. Nigel Galloway: February 1st., 2023
open Mathnet.Numerics
let fN(g:BigRational)=match bigint.DivRem(g.Denominator,g.Numerator) with (n,g) when g=0I->n |(n,_)->n+1I
let fG(n:BigRational)=Seq.unfold(fun(g:BigRational)->if g.Numerator=0I then None else let i=fN g in Some(i,(g-1N/(BigRational.FromBigInt i))))(n)
let fL(n:bigint,g:seq<bigint>)=printf "%A" n; g|>Seq.iter(printf "+1/%A"); printfn ""
let f2ef(i:BigRational)=let n,g=bigint.DivRem(i.Numerator,i.Denominator) in (n,fG(BigRational.FromBigIntFraction(g,i.Denominator)))
[43N/48N;5N/121N;2014N/59N]|>List.iter(f2ef>>fL)
let n,_=List.allPairs [1N..99N] [1N..99N]|>Seq.map(fun(n,g)->let n=n/g in (n,f2ef n))|>Seq.maxBy(fun(_,(n,g))->Seq.length g + if n>0I then 1 else 0) in printf "%A->" n; (f2ef>>fL)n
let n,_=List.allPairs [1N..999N] [1N..999N]|>Seq.map(fun(n,g)->let n=n/g in (n,f2ef n))|>Seq.maxBy(fun(_,(n,g))->Seq.length g + if n>0I then 1 else 0) in printf "%A->" n; (f2ef>>fL)n
let n,_=List.allPairs [1N..99N] [1N..99N]|>Seq.map(fun(n,g)->let n=n/g in (n,f2ef n))|>Seq.maxBy(fun(_,(n,g))->if Seq.isEmpty g then 0I else Seq.max g) in printf "%A->" n; (f2ef>>fL)n
let n,_=List.allPairs [1N..999N] [1N..999N]|>Seq.map(fun(n,g)->let n=n/g in (n,f2ef n))|>Seq.maxBy(fun(_,(n,g))->if Seq.isEmpty g then 0I else Seq.max g) in printf "%A->" n; (f2ef>>fL)n
</syntaxhighlight>
{{out}}
<pre>
0+1/2+1/3+1/16
0+1/25+1/757+1/763309+1/873960180913+1/1527612795642093418846225
34+1/8+1/95+1/14947+1/670223480
97/53N->1+1/2+1/4+1/13+1/307+1/120871+1/20453597227+1/697249399186783218655+1/1458470173998990524806872692984177836808420
493/457N->1+1/13+1/541+1/321409+1/114781617793+1/14821672255960844346913+1/251065106814993628596500876449600804290086881+1/73539302503361520198362339236500915390885795679264404865887253300925727812630083326272641+1/6489634815217096741758907148982381236931234341288936993640630568353888026513046373352130623124225014404918014072680355409470797372507720812828610332359154836067922616607391865217+1/52644200043597301715163084170074049765863371513744701000308778672552161021188727897845435784419167578097570308323221316037189809321236639774156001218848770417914304730719451756764847141999454715415348579218576135692260706546084789833559164567239198064491721524233401718052341737694961761810858726456915514545036448002629051435498625211733293978125476206145+1/3695215730973720191743335450900515442837964059737103132125137784392340041085824276783333540815086968586494259680343732030671448522298751008735945486795776365973142745077411841504712940444458881229478108614230774637316342940593842925604630011475333378620376362943942755446627099104200059416153812858633723638212819657597061963458758259287734950993940819872945202809437805131650984566124057319228963533088559443909352453788455968978250113376533423265233637558939144535732287317303130488802163512444658441011602922480039143050047663394967808639154754442570791381496210122415541628843804495020590646687354364355396925939868087995781911240513904752765014910531863571167632659092232428610030201325032663259931238141889+1/20481928947653467858867964360215698922460866349989714221296388791180533521147068328398292448571350580917144516243144419767021450972552458770890215041236338405232471846144964422722088363577942656244304369314740680337368003341749927848292268159627280776486153786277410225081205358330757686606252814923029488556248114378465151886875778980493919811102286892641254175976181063891774788890129279669791215911728886439002027991447164421080590166911130116483359749418047307595497010369457711350953018694479942850146580996402187310635505278301929397030213544531068769667892360925519410013180703331321321833900350008776368272790481252519169303988218210095146759870287941250090204506960847016059468728275311477613271084474766715488264771177830115028195215223644336345646870679050787515340804351339449474385172464387868299006904638274425855008729765086091731260299397062138670321522563954731398813138738073326593694555049353805161855854036423870334342280080335804850998490793742536882308453307029152812821729798744074167237835462214043679643723245065093600037959124662392297413473130606861784229249604290090458912391096328362137163951398211801143455350336317188806956746282700489013366856863803112203078858200161688528939040348825835610989725020068306497091337571398894447440161081470240965873628208205669354804691958270783090585006358905094926094885655359774269830169287513005586562246433405044654325439410730648108371520856384706590593+1/839018826833450186636781520007011999269820404906753180244759299287837378895397605613261469995626498719289835112392530430840514102146998625666594756995273418015600023494049208108894185781774002683063204252356172520941088783702738286944210460710059319691268110283467445381026653628599765684739105388642310044785844902157076919003735231543781785073393176144167688252446541416466418608465458502997971425428342769433127784560570193376772878336217849260872114137931351960543608384244009505664253173875705234889570853924105640193619301332776989688248555027054395237907581951261868280899150574360164800187964167274323078311078867593844043149124596271281252530924719121766925749760855109100066731841478262812686642693395896229983745226277793055820609058348269152190083695704685769622011655159174272326647342695589818127126303038171968768650476413027459205291075571637957597356820188031655122749743652301268394542123970892422944335857917641636041892192547135178153602038877677614358281581103685526041329841496863410305888255234495015115912388514981113593387572720476744188169200130515719608747338810136728267784013352396910979904545913458536243327311977805126410065576961237640824852114328884086581542091492600312838425666927627674227053793897767395465326589843035773944346372949759909905561209334216847158156644884281300512699910530092870919061876615770708519243818676366245477462042294267674677954783726990349386117468071932874021023714524610740225814235147693954027910741673103980749749728106483987721602738673173009362802337092908847797499475895347112889339502928407808058670297722175686638678788738689803945574002805677250463286479363670076942509109589495377221095405979217163821481666646160815221224686562530536116613645305335922819524037829878961518170177968768364853399057357772141655622381280196908637031556436461404285930426436983658106288733881761514992109680298995922754466040011586713812553117621857109517258943846004179432521131844156242428351270188803919554398620084668514054504414062276012292497375238210886595006249453460414790147611422121782194848803348777061816460876697945418158442269512987729152441940326466631610424906158237288218706447963113019239557885486647314085357651895226117364760315394354624547919209138539180807829672545924239541758108877100331729470119526373928796447673951888289511964811633025369821156695934557103429921063387965046715070102916811976552584464153981214277622597308113449320462341683055200576571910241686615924531368198770946893858410058348221985603151428153382461711196734214085852523778422630907646235900752317571022131569421231196329080023952364788544301495422061066036911772385739659997665503832444529713544286955548310166168837889046149061296461059432238621602179724809510024772127497080258401694929973105184832214622785679651550368465524821062859837409907538269572622296774545103747438431266995525592705
8/97N->0+1/13+1/181+1/38041+1/1736503177+1/3769304102927363485+1/18943537893793408504192074528154430149+1/538286441900380211365817285104907086347439746130226973253778132494225813153+1/579504587067542801713103191859918608251030291952195423583529357653899418686342360361798689053273749372615043661810228371898539583862011424993909789665
36/457N->0+1/13+1/541+1/321409+1/114781617793+1/14821672255960844346913+1/251065106814993628596500876449600804290086881+1/73539302503361520198362339236500915390885795679264404865887253300925727812630083326272641+1/6489634815217096741758907148982381236931234341288936993640630568353888026513046373352130623124225014404918014072680355409470797372507720812828610332359154836067922616607391865217+1/52644200043597301715163084170074049765863371513744701000308778672552161021188727897845435784419167578097570308323221316037189809321236639774156001218848770417914304730719451756764847141999454715415348579218576135692260706546084789833559164567239198064491721524233401718052341737694961761810858726456915514545036448002629051435498625211733293978125476206145+1/3695215730973720191743335450900515442837964059737103132125137784392340041085824276783333540815086968586494259680343732030671448522298751008735945486795776365973142745077411841504712940444458881229478108614230774637316342940593842925604630011475333378620376362943942755446627099104200059416153812858633723638212819657597061963458758259287734950993940819872945202809437805131650984566124057319228963533088559443909352453788455968978250113376533423265233637558939144535732287317303130488802163512444658441011602922480039143050047663394967808639154754442570791381496210122415541628843804495020590646687354364355396925939868087995781911240513904752765014910531863571167632659092232428610030201325032663259931238141889+1/20481928947653467858867964360215698922460866349989714221296388791180533521147068328398292448571350580917144516243144419767021450972552458770890215041236338405232471846144964422722088363577942656244304369314740680337368003341749927848292268159627280776486153786277410225081205358330757686606252814923029488556248114378465151886875778980493919811102286892641254175976181063891774788890129279669791215911728886439002027991447164421080590166911130116483359749418047307595497010369457711350953018694479942850146580996402187310635505278301929397030213544531068769667892360925519410013180703331321321833900350008776368272790481252519169303988218210095146759870287941250090204506960847016059468728275311477613271084474766715488264771177830115028195215223644336345646870679050787515340804351339449474385172464387868299006904638274425855008729765086091731260299397062138670321522563954731398813138738073326593694555049353805161855854036423870334342280080335804850998490793742536882308453307029152812821729798744074167237835462214043679643723245065093600037959124662392297413473130606861784229249604290090458912391096328362137163951398211801143455350336317188806956746282700489013366856863803112203078858200161688528939040348825835610989725020068306497091337571398894447440161081470240965873628208205669354804691958270783090585006358905094926094885655359774269830169287513005586562246433405044654325439410730648108371520856384706590593+1/839018826833450186636781520007011999269820404906753180244759299287837378895397605613261469995626498719289835112392530430840514102146998625666594756995273418015600023494049208108894185781774002683063204252356172520941088783702738286944210460710059319691268110283467445381026653628599765684739105388642310044785844902157076919003735231543781785073393176144167688252446541416466418608465458502997971425428342769433127784560570193376772878336217849260872114137931351960543608384244009505664253173875705234889570853924105640193619301332776989688248555027054395237907581951261868280899150574360164800187964167274323078311078867593844043149124596271281252530924719121766925749760855109100066731841478262812686642693395896229983745226277793055820609058348269152190083695704685769622011655159174272326647342695589818127126303038171968768650476413027459205291075571637957597356820188031655122749743652301268394542123970892422944335857917641636041892192547135178153602038877677614358281581103685526041329841496863410305888255234495015115912388514981113593387572720476744188169200130515719608747338810136728267784013352396910979904545913458536243327311977805126410065576961237640824852114328884086581542091492600312838425666927627674227053793897767395465326589843035773944346372949759909905561209334216847158156644884281300512699910530092870919061876615770708519243818676366245477462042294267674677954783726990349386117468071932874021023714524610740225814235147693954027910741673103980749749728106483987721602738673173009362802337092908847797499475895347112889339502928407808058670297722175686638678788738689803945574002805677250463286479363670076942509109589495377221095405979217163821481666646160815221224686562530536116613645305335922819524037829878961518170177968768364853399057357772141655622381280196908637031556436461404285930426436983658106288733881761514992109680298995922754466040011586713812553117621857109517258943846004179432521131844156242428351270188803919554398620084668514054504414062276012292497375238210886595006249453460414790147611422121782194848803348777061816460876697945418158442269512987729152441940326466631610424906158237288218706447963113019239557885486647314085357651895226117364760315394354624547919209138539180807829672545924239541758108877100331729470119526373928796447673951888289511964811633025369821156695934557103429921063387965046715070102916811976552584464153981214277622597308113449320462341683055200576571910241686615924531368198770946893858410058348221985603151428153382461711196734214085852523778422630907646235900752317571022131569421231196329080023952364788544301495422061066036911772385739659997665503832444529713544286955548310166168837889046149061296461059432238621602179724809510024772127497080258401694929973105184832214622785679651550368465524821062859837409907538269572622296774545103747438431266995525592705
</pre>
=={{header|Factor}}==
<syntaxhighlight lang="factor">USING: backtrack formatting fry kernel locals make math
Line 1,091 ⟶ 1,118:
=={{header|Fōrmulæ}}==
 
{{FormulaeEntry|page=https://formulae.org/?script=examples/Egyptian_fractions}}
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation &mdash;i.e. XML, JSON&mdash; they are intended for storage and transfer purposes more than visualization and edition.
 
'''Solution'''
Programs in Fōrmulæ are created/edited online in its [https://formulae.org website], However they run on execution servers. By default remote servers are used, but they are limited in memory and processing power, since they are intended for demonstration and casual use. A local server can be downloaded and installed, it has no limitations (it runs in your own computer). Because of that, example programs can be fully visualized and edited, but some of them will not run if they require a moderate or heavy computation/memory resources, and no local server is being used.
 
[[File:Fōrmulæ - Egyptian fractions 01.png]]
In '''[https://formulae.org/?example=Egyptian_fractions this]''' page you can see the program(s) related to this task and their results.
 
'''Test cases part 1'''
 
[[File:Fōrmulæ - Egyptian fractions 02.png]]
 
[[File:Fōrmulæ - Egyptian fractions 03.png]]
 
[[File:Fōrmulæ - Egyptian fractions 04.png]]
 
[[File:Fōrmulæ - Egyptian fractions 05.png]]
 
[[File:Fōrmulæ - Egyptian fractions 06.png]]
 
[[File:Fōrmulæ - Egyptian fractions 07.png]]
 
'''Test cases part 2'''
 
[[File:Fōrmulæ - Egyptian fractions 08.png]]
 
[[File:Fōrmulæ - Egyptian fractions 09.png]]
 
[[File:Fōrmulæ - Egyptian fractions 10.png]]
 
[[File:Fōrmulæ - Egyptian fractions 11.png]]
 
[[File:Fōrmulæ - Egyptian fractions 12.png]]
 
[[File:Fōrmulæ - Egyptian fractions 13.png]]
 
[[File:Fōrmulæ - Egyptian fractions 14.png]]
 
=={{header|Go}}==
Line 2,908 ⟶ 2,965:
largest denominator in the Egyptian fractions is 2847 digits is for 36/457
</pre>
 
=={{header|RPL}}==
<code>GCD</code> is defined at [[Greatest common divisor#RPL|Greatest common divisor]]
{{works with|Halcyon Calc|4.2.7}}
{| class="wikitable" ≪
! RPL code
! Comment
|-
|
≪
DUP IM LAST RE / CEIL
SWAP RE LAST IM DUP NEG ROT MOD
SWAP 3 PICK *
DUP2 <span style="color:blue">GCD</span> ROT OVER / ROT ROT / R→C
≫ '<span style="color:blue">SPLIT</span>' STO
≪
DUP 3 EXGET SWAP 1 EXGET
'''IF''' DUP2 > '''THEN'''
SWAP OVER MOD LAST / IP SWAP ROT
'''ELSE''' 0 ROT ROT '''END'''
R→C
'''WHILE''' DUP RE '''REPEAT'''
<span style="color:blue">SPLIT</span>
"'1/" ROT →STR + "'" + STR→
ROT SWAP + SWAP
'''END'''
≫ '<span style="color:blue">EGYPF</span>' STO
|
<span style="color:blue">SPLIT</span> ''( (x1,y1) → n1 (x2,y2) ) ''
n1 = ceil(y1/x1)
x2 = mod(-y1,x1)
y2 = n1*y1
simplify x2/y2
<span style="color:blue">EGYPF</span> ''( 'x/y' → 'sum_of_Egyptian_fractions') ''
put x and y in stack
if x > y
first term of sum is x//y and x = mod(x,y)
else first term is 0
convert to complex to ease handling in stack
loop while x<sub>k</sub> ≠ 0
get n<sub>k</sub> and (x<sub>k</sub>, y<sub>k</sub>)
convert n<sub>k</sub> into '1/n<sub>k</sub>'
add '1/n<sub>k</sub>' to the sum
end loop
return sum
|}
'43/48' <span style="color:blue">EGYPF</span>
'5/121' <span style="color:blue">EGYPF</span>
'2014/59' <span style="color:blue">EGYPF</span>
{{out}}
<pre>
3: 'INV(2)+INV(3)+INV(16)'
2: 'INV(25)+INV(757)+INV(763309)+INV(873960180913)+INV(1.52761279564E+24)'
1: '34+INV(8)+INV(95)+INV(14947)+INV(670223480)'
</pre>
In algebraic expressions, RPL automatically replaces <code>1/n</code> by <code>INV(n)</code>
====Quest for the largest number of items for proper fractions 2.99/2..99====
≪ '1/1' 0
2 99 '''FOR''' d 2 d 1 - '''FOR''' n
"'" n →STR + "/" + d →STR + "'" + STR→
DUP <span style="color:blue">EGYPF</span> SIZE → f sf
≪ '''IF''' sf OVER > '''THEN''' DROP2 f sf '''END''' ≫
'''NEXT NEXT''' DROP
≫ '<span style="color:blue">TASK</span>'
{{out}}
<pre>
1: '44/53'
</pre>
Limited precision of basic RPL prevents from searching the largest denominator.
 
=={{header|Ruby}}==
Line 3,640 ⟶ 3,769:
{{libheader|Wren-big}}
We use the BigRat class in the above module to represent arbitrary size fractions.
<syntaxhighlight lang="ecmascriptwren">import "./big" for BigInt, BigRat
 
var toEgyptianHelper // recursive
GordonCharlton
1,462

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/327454...352434"