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

16,970 bytes added ,  5 months ago
Added link to numberphile video
m (Updated description and link for Fōrmulæ solution)
(Added link to numberphile video)
 
(10 intermediate revisions by 6 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 47 ⟶ 48:
Based on the VB.NET sample.<br>
Uses Algol 68G's LONG LONG INT for large integers.
<langsyntaxhighlight lang="algol68">BEGIN # compute some Egytian fractions #
PR precision 2000 PR # set the number of digits for LONG LONG INT #
PROC gcd = ( LONG LONG INT a, b )LONG LONG INT:
Line 162 ⟶ 163:
)
END
END</langsyntaxhighlight>
{{out}}
<pre>
Line 177 ⟶ 178:
=={{header|C}}==
Output has limited accuracy as noted by comments. The problem requires bigint support to be completely accurate.
<langsyntaxhighlight lang="c">#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
Line 290 ⟶ 291:
 
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>Egyptian fraction for 43/48: 1/2 + 1/3 + 1/16
Line 301 ⟶ 302:
=={{header|C sharp|C#}}==
{{trans|Visual Basic .NET}}
<langsyntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
using System.Linq;
Line 448 ⟶ 449:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>43/48 => [1/2, 1/3, 1/16]
Line 459 ⟶ 460:
{{libheader|Boost}}
The C++ standard library does not have a "big integer" type, so this solution uses the Boost library.
<langsyntaxhighlight lang="cpp">#include <iostreamboost/multiprecision/cpp_int.hpp>
#include <iostream>
#include <optional>
#include <sstream>
#include <string>
#include <vector>
#include <string>
#include <sstream>
#include <boost/multiprecision/cpp_int.hpp>
 
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 572 ⟶ 575:
show_max_terms_and_max_denominator(1000);
return 0;
}</langsyntaxhighlight>
 
{{out}}
Line 595 ⟶ 598:
 
=={{header|Common Lisp}}==
<langsyntaxhighlight lang="lisp">(defun egyption-fractions (x y &optional acc)
(let* ((a (/ x y)))
(cond
Line 613 ⟶ 616:
#'>
:key #'cdr)))
</syntaxhighlight>
</lang>
 
{{out}}
Line 642 ⟶ 645:
Assuming the Python entry is correct, this code is equivalent. This requires the D module of the Arithmetic/Rational task.
{{trans|Python}}
<langsyntaxhighlight lang="d">import std.stdio, std.bigint, std.algorithm, std.range, std.conv, std.typecons,
arithmetic_rational: Rat = Rational;
 
Line 689 ⟶ 692:
writefln("Denominator max is %s with %d digits %s...%s",
denomMax[1], dStr.length, dStr[0 .. 5], dStr[$ - 5 .. $]);
}</langsyntaxhighlight>
{{out}}
<pre>43/48 => 1/2 1/3 1/16
Line 698 ⟶ 701:
 
=={{header|Erlang}}==
<langsyntaxhighlight lang="erlang">-module(egypt).
 
-import(lists, [reverse/1, seq/2]).
Line 759 ⟶ 762:
true -> B
end.
</syntaxhighlight>
</lang>
 
{{out}}
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}}==
<langsyntaxhighlight lang="factor">USING: backtrack formatting fry kernel locals make math
math.functions math.ranges sequences ;
IN: rosetta-code.egyptian-fractions
Line 822 ⟶ 849:
: egyptian-fractions-demo ( -- ) part1 part2 ;
 
MAIN: egyptian-fractions-demo</langsyntaxhighlight>
{{out}}
<pre>
Line 834 ⟶ 861:
=={{header|FreeBASIC}}==
{{libheader|GMP}}
<langsyntaxhighlight lang="freebasic">' version 16-01-2017
' compile with: fbc -s console
 
Line 1,002 ⟶ 1,029:
Print : Print "hit any key to end program"
Sleep
End</langsyntaxhighlight>
{{out}}
<pre>43/48 = 1/2 + 1/3 + 1/16
Line 1,020 ⟶ 1,047:
 
=={{header|Frink}}==
<syntaxhighlight lang="frink">
<lang Frink>
frac[p, q] :=
{
Line 1,072 ⟶ 1,099:
println["The fraction with the largest denominator is $biggest"]
}
</syntaxhighlight>
</lang>
{{Out}}
<pre>
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}}==
{{trans|Kotlin}}
... except that Go already has support for arbitrary precision rational numbers in its standard library.
<langsyntaxhighlight lang="go">package main
 
import (
Line 1,236 ⟶ 1,293:
fmt.Println(" fraction(s) with this denominator :", maxDenFracs)
}
}</langsyntaxhighlight>
 
{{out}}
Line 1,258 ⟶ 1,315:
 
=={{header|Haskell}}==
<langsyntaxhighlight lang="haskell">import Data.Ratio (Ratio, (%), denominator, numerator)
 
egyptianFraction :: Integral a => Ratio a -> [Ratio a]
Line 1,270 ⟶ 1,327:
x = numerator n
y = denominator n
r = y `div` x + 1</langsyntaxhighlight>
 
'''Testing''':
<langsyntaxhighlight lang="haskell">λ> :m Test.QuickCheck
λ> quickCheck (\n -> n == (sum $ egyptianFraction n))
+++ OK, passed 100 tests.</langsyntaxhighlight>
 
'''Tasks''':
<langsyntaxhighlight lang="haskell">import Data.List (intercalate, maximumBy)
import Data.Ord (comparing)
 
Line 1,300 ⟶ 1,357:
| a <- [1 .. n]
, b <- [1 .. n]
, a < b ]</langsyntaxhighlight>
 
<langsyntaxhighlight lang="haskell">λ> task1
43 % 48 = 1 % 2 + 1 % 3 + 1 % 16
5 % 121 = 1 % 25 + 1 % 757 + 1 % 763309 + 1 % 873960180913 + 1 % 1527612795642093418846225
Line 1,314 ⟶ 1,371:
λ> task22 999
(529 % 914, 839018826833450186636781520007011999269820404906753180244759299287837378895397605613261469995626498719289835112392530430840514102146998625666594756995273418015600023494049208108894185781774002683063204252356172520941088783702738286944210460710059319691268110283467445381026653628599765684739105388642310044785844902157076919003735231543781785073393176144167688252446541416466418608465458502997971425428342769433127784560570193376772878336217849260872114137931351960543608384244009505664253173875705234889570853924105640193619301332776989688248555027054395237907581951261868280899150574360164800187964167274323078311078867593844043149124596271281252530924719121766925749760855109100066731841478262812686642693395896229983745226277793055820609058348269152190083695704685769622011655159174272326647342695589818127126303038171968768650476413027459205291075571637957597356820188031655122749743652301268394542123970892422944335857917641636041892192547135178153602038877677614358281581103685526041329841496863410305888255234495015115912388514981113593387572720476744188169200130515719608747338810136728267784013352396910979904545913458536243327311977805126410065576961237640824852114328884086581542091492600312838425666927627674227053793897767395465326589843035773944346372949759909905561209334216847158156644884281300512699910530092870919061876615770708519243818676366245477462042294267674677954783726990349386117468071932874021023714524610740225814235147693954027910741673103980749749728106483987721602738673173009362802337092908847797499475895347112889339502928407808058670297722175686638678788738689803945574002805677250463286479363670076942509109589495377221095405979217163821481666646160815221224686562530536116613645305335922819524037829878961518170177968768364853399057357772141655622381280196908637031556436461404285930426436983658106288733881761514992109680298995922754466040011586713812553117621857109517258943846004179432521131844156242428351270188803919554398620084668514054504414062276012292497375238210886595006249453460414790147611422121782194848803348777061816460876697945418158442269512987729152441940326466631610424906158237288218706447963113019239557885486647314085357651895226117364760315394354624547919209138539180807829672545924239541758108877100331729470119526373928796447673951888289511964811633025369821156695934557103429921063387965046715070102916811976552584464153981214277622597308113449320462341683055200576571910241686615924531368198770946893858410058348221985603151428153382461711196734214085852523778422630907646235900752317571022131569421231196329080023952364788544301495422061066036911772385739659997665503832444529713544286955548310166168837889046149061296461059432238621602179724809510024772127497080258401694929973105184832214622785679651550368465524821062859837409907538269572622296774545103747438431266995525592705)
</syntaxhighlight>
</lang>
 
=={{header|J}}==
'''Solution''':<langsyntaxhighlight lang="j"> ef =: [: (}.~ 0={.) [: (, r2ef)/ 0 1 #: x:
r2ef =: (<(<0);0) { ((] , -) >:@:<.&.%)^:((~:<.)@:%)@:{:^:a:</langsyntaxhighlight>
'''Examples''' (''required''):<langsyntaxhighlight lang="j"> (; ef)&> 43r48 5r121 2014r59
+-------+--------------------------------------------------------------+
|43r48 |1r2 1r3 1r16 |
Line 1,327 ⟶ 1,384:
+-------+--------------------------------------------------------------+
|2014r59|34 1r8 1r95 1r14947 1r670223480 |
+-------+--------------------------------------------------------------+</langsyntaxhighlight>
 
'''Examples''' (''extended''):<langsyntaxhighlight lang="j"> NB. ef for all 1- and 2-digit fractions
EF2 =: ef :: _1:&.> (</~ * %/~) i. 10^2x
 
Line 1,394 ⟶ 1,451:
52971354428695554831016616883788904614906129646105943223862160217972480951002477
21274970802584016949299731051848322146227856796515503684655248210628598374099075
38269572622296774545103747438431266995525592705 </langsyntaxhighlight>
 
=={{header|Java}}==
{{trans|Kotlin}}
{{works with|Java|9}}
<langsyntaxhighlight Javalang="java">import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.MathContext;
Line 1,609 ⟶ 1,666:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>43/48 -> 1/2 + 1/3 + 1/16
Line 1,630 ⟶ 1,687:
{{works with|Julia|0.6}}
 
<langsyntaxhighlight lang="julia">struct EgyptianFraction{T<:Integer} <: Real
int::T
frac::NTuple{N,Rational{T}} where N
Line 1,695 ⟶ 1,752:
frlenmax, lenmax, frdenmax, denmax = task(fr)
println("Longest fraction, with length $lenmax: \n", Rational(frlenmax), "\n = ", frlenmax)
println("Fraction with greatest denominator\n(that is $denmax):\n", Rational(frdenmax), "\n = ", frdenmax)</langsyntaxhighlight>
 
{{out}}
Line 1,731 ⟶ 1,788:
=={{header|Kotlin}}==
As the JDK lacks a fraction or rational class, I've included a basic one in the program.
<langsyntaxhighlight lang="scala">// version 1.2.10
 
import java.math.BigInteger
Line 1,898 ⟶ 1,955:
println(" fraction(s) with this denominator : $maxDenFracs")
}
}</langsyntaxhighlight>
 
{{out}}
Line 1,920 ⟶ 1,977:
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<langsyntaxhighlight Mathematicalang="mathematica">frac[n_] /; IntegerQ[1/n] := frac[n] = {n};
frac[n_] :=
frac[n] =
Line 1,941 ⟶ 1,998:
fracs = Flatten[Table[frac[p/q], {q, 999}, {p, q}], 1];
Print[disp[MaximalBy[fracs, Length@*Union][[1]]]];
Print[disp[MaximalBy[fracs, Denominator@*Last][[1]]]];</langsyntaxhighlight>
{{out}}
<pre>1/2 + 1/3 + 1/16 = 43/48
Line 1,953 ⟶ 2,010:
=={{header|Microsoft Small Basic}}==
Small Basic but large (not huge) integers.
<langsyntaxhighlight lang="smallbasic">'Egyptian fractions - 26/07/2018
xx=2014
yy=59
Line 2,006 ⟶ 2,063:
EndWhile
ret=wx
EndSub </langsyntaxhighlight>
{{out}}
43/48=1/2+1/3
Line 2,015 ⟶ 2,072:
{{trans|Go}}
{{libheader|bignum}}
<langsyntaxhighlight Nimlang="nim">import strformat, strutils
import bignum
 
Line 2,112 ⟶ 2,169:
let md = $maxDen
echo fmt" largest denominator = {md.len} digits, {md[0..19]}...{md[^20..^1]}"
echo fmt" fraction(s) with this denominator : {maxDenFracs.join("", "")}"</langsyntaxhighlight>
 
{{out}}
Line 2,132 ⟶ 2,189:
 
=={{header|PARI/GP}}==
<langsyntaxhighlight lang="parigp">
efrac(f)=my(v=List());while(f,my(x=numerator(f),y=denominator(f));listput(v,ceil(y/x));f=(-y)%x/y/v[#v]);Vec(v);
show(f)=my(n=f\1,v=efrac(f-n)); print1(f" = ["n"; "v[1]); for(i=2,#v,print1(", "v[i])); print("]");
Line 2,140 ⟶ 2,197:
best(99)
best(999)
</syntaxhighlight>
</lang>
{{out}}
<pre>43/48 = [0; 2, 3, 16]
Line 2,156 ⟶ 2,213:
 
=={{header|Perl}}==
<langsyntaxhighlight lang="perl">use strict;
use warnings;
use bigint;
Line 2,191 ⟶ 2,248:
printf "\nEgyptian Fraction Representation of " . $nrI . "/" . $deI . " is: \n\n";
isEgyption($nrI,$deI);
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 2,202 ⟶ 2,259:
{{libheader|Phix/mpfr}}
The sieve copied from Go
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
Line 2,281 ⟶ 2,338:
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Largest size for denominator is %d digits (%s) for %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">maxd</span><span style="color: #0000FF;">,</span><span style="color: #000000;">maxda</span><span style="color: #0000FF;">,</span><span style="color: #000000;">maxds</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 2,299 ⟶ 2,356:
=={{header|Prolog}}==
{{works with|SWI Prolog}}
<langsyntaxhighlight lang="prolog">count_digits(Number, Count):-
atom_number(A, Number),
atom_length(A, Count).
Line 2,395 ⟶ 2,452:
show_max_terms_and_denominator(100),
nl,
show_max_terms_and_denominator(1000).</langsyntaxhighlight>
 
{{out}}
Line 2,414 ⟶ 2,471:
=={{header|Python}}==
===Procedural===
<langsyntaxhighlight lang="python">from fractions import Fraction
from math import ceil
 
Line 2,451 ⟶ 2,508:
dstr = str(denommax[0])
print('Denominator max is %r with %i digits %s...%s' %
(denommax[1], len(dstr), dstr[:5], dstr[-5:]))</langsyntaxhighlight>
 
{{out}}
Line 2,465 ⟶ 2,522:
See the '''unfoldr''' function below:
{{Works with|Python|3.7}}
<langsyntaxhighlight lang="python">'''Egyptian fractions'''
 
from fractions import Fraction
Line 2,604 ⟶ 2,661:
# MAIN ---
if __name__ == '__main__':
main()</langsyntaxhighlight>
{{Out}}
<pre>Three values as Eqyptian fractions:
Line 2,625 ⟶ 2,682:
=={{header|Racket}}==
 
<langsyntaxhighlight lang="racket">#lang racket
(define (real->egyptian-list R)
(define (inr r rv)
Line 2,673 ⟶ 2,730:
 
(module+ test (require tests/eli-tester)
(test (real->egyptian-list 43/48) => '(1/2 1/3 1/16)))</langsyntaxhighlight>
 
{{out}}
Line 2,742 ⟶ 2,799:
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku" perl6line>role Egyptian {
method gist {
join ' + ',
Line 2,771 ⟶ 2,828:
" has max number of denominators, namely ",
.value.elems
given max :by(*.value.elems), @sample;</langsyntaxhighlight>
{{out}}
<pre>43/48 = 1/2 + 1/3 + 1/16
Line 2,781 ⟶ 2,838:
Because the harmonic series diverges (albeit very slowly), it is possible to write even improper fractions as a sum of distinct unit fractions. Here is a code to do that:
 
<syntaxhighlight lang="raku" perl6line>role Egyptian {
method gist { join ' + ', map {"1/$_"}, self.list }
method list {
Line 2,792 ⟶ 2,849:
}
say 5/4 but Egyptian;</langsyntaxhighlight>
{{out}}
<pre>1/2 + 1/3 + 1/4 + 1/6</pre>
Line 2,799 ⟶ 2,856:
 
=={{header|REXX}}==
<langsyntaxhighlight lang="rexx">/*REXX program converts a fraction (can be improper) to an Egyptian fraction. */
parse arg fract '' -1 t; z=$egyptF(fract) /*compute the Egyptian fraction. */
if t\==. then say fract ' ───► ' z /*show Egyptian fraction from C.L.*/
Line 2,851 ⟶ 2,908:
gcd:procedure;$=;do i=1 for arg();$=$ arg(i);end;parse var $ x z .;if x=0 then x=z;x=abs(x);do j=2 to words($);y=abs(word($,j));if y=0 then iterate;do until _==0;_=x//y;x=y;y=_;end;end;return x
lcm:procedure;y=;do j=1 for arg();y=y arg(j);end;x=word(y,1);do k=2 to words(y);!=abs(word(y,k));if !=0 then return 0;x=x*!/gcd(x,!);end;return x
p: return word(arg(1),1)</langsyntaxhighlight>
'''output''' &nbsp; when the input used is: &nbsp; <tt> 43/48 </tt>
<pre>
Line 2,873 ⟶ 2,930:
 
Also, the same program is used for the 1-, 2-, and 3-digit extra credit task.
<langsyntaxhighlight lang="rexx">/*REXX pgm runs the EGYPTIAN program to find biggest denominator & # of terms.*/
parse arg top . /*get optional parameter from the C.L. */
if top=='' then top=99 /*Not specified? Then use the default.*/
Line 2,896 ⟶ 2,953:
say
say 'highest denominator' @ length(maxD) "digits for" bigD
if oTop>0 then say maxD /*stick a fork in it, we're all done. */</langsyntaxhighlight>
'''output''' &nbsp; for all 1- and 2-digit integers when using the default input:
<pre>
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}}==
{{trans|Python}}
<langsyntaxhighlight lang="ruby">def ef(fr)
ans = []
if fr >= 1
Line 2,943 ⟶ 3,072:
puts 'Term max is %s with %i terms' % [lenmax[1], lenmax[0]]
dstr = denommax[0].to_s
puts 'Denominator max is %s with %i digits' % [denommax[1], dstr.size], dstr</langsyntaxhighlight>
 
{{out}}
Line 2,956 ⟶ 3,085:
 
=={{header|Rust}}==
<langsyntaxhighlight lang="rust">
use num_bigint::BigInt;
use num_integer::Integer;
Line 3,096 ⟶ 3,225:
}
 
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 3,113 ⟶ 3,242:
=={{header|Scala}}==
{{trans|Java}}
<langsyntaxhighlight lang="scala">import scala.annotation.tailrec
import scala.collection.mutable
import scala.collection.mutable.{ArrayBuffer, ListBuffer}
Line 3,319 ⟶ 3,448:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>43/48 -> 1/2 + 1/3 + 1/16
Line 3,339 ⟶ 3,468:
=={{header|Sidef}}==
{{trans|Ruby}}
<langsyntaxhighlight lang="ruby">func ef(fr) {
var ans = []
if (fr >= 1) {
Line 3,374 ⟶ 3,503:
"Term max is %s with %i terms\n".printf(lenmax[1].as_rat, lenmax[0])
"Denominator max is %s with %i digits\n".printf(denommax[1].as_rat, denommax[0].size)
say denommax[0]</langsyntaxhighlight>
{{out}}
<pre>
Line 3,386 ⟶ 3,515:
 
=={{header|Tcl}}==
<langsyntaxhighlight lang="tcl"># Just compute the denominator terms, as the numerators are always 1
proc egyptian {num denom} {
set result {}
Line 3,397 ⟶ 3,526:
}
return $result
}</langsyntaxhighlight>
Demonstrating:
{{works with|Tcl|8.6}}
<langsyntaxhighlight lang="tcl">package require Tcl 8.6
 
proc efrac {fraction} {
Line 3,434 ⟶ 3,563:
}
puts "$maxtf has maximum number of terms = [efrac $maxtf]"
puts "$maxdf has maximum denominator = [efrac $maxdf]"</langsyntaxhighlight>
{{out}}
<pre>
Line 3,448 ⟶ 3,577:
=={{header|Visual Basic .NET}}==
{{trans|D}}
<langsyntaxhighlight lang="vbnet">Imports System.Numerics
Imports System.Text
 
Line 3,628 ⟶ 3,757:
End Sub
 
End Module</langsyntaxhighlight>
{{out}}
<pre>43/48 => [1/2, 1/3, 1/16]
Line 3,640 ⟶ 3,769:
{{libheader|Wren-big}}
We use the BigRat class in the above module to represent arbitrary size fractions.
<langsyntaxhighlight ecmascriptlang="wren">import "./big" for BigInt, BigRat
 
var toEgyptianHelper // recursive
Line 3,731 ⟶ 3,860:
System.print("%(md[0...20])...%(md[-20..-1])")
System.print(" fraction(s) with this denominator : %(maxDenFracs)")
}</langsyntaxhighlight>
 
{{out}}
Line 3,754 ⟶ 3,883:
=={{header|zkl}}==
{{trans|Tcl}}
<langsyntaxhighlight lang="zkl"># Just compute the denominator terms, as the numerators are always 1
fcn egyptian(num,denom){
result,t := List(),Void;
Line 3,774 ⟶ 3,903:
else String("1/",denom);
}).concat(" + ")
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">foreach n,d in (T(T(43,48), T(5,121), T(2014,59))){
println("%s/%s --> %s".fmt(n,d, egyptian(n,d):efrac(_)));
}</langsyntaxhighlight>
{{out}}
<pre>
Line 3,785 ⟶ 3,914:
</pre>
For the big denominators, use GMP (Gnu Multi Precision).
<langsyntaxhighlight lang="zkl">var [const] BN=Import("zklBigNum"); // libGMP
lenMax,denomMax := List(0,Void),List(0,Void);
foreach n,d in (Walker.cproduct([1..99],[1..99])){ // 9801 fractions
Line 3,796 ⟶ 3,925:
dStr:=denomMax[0].toString();
println("Denominator max is %s/%s with %d digits %s...%s"
.fmt(denomMax[1].xplode(), dStr.len(), dStr[0,5], dStr[-5,*]));</langsyntaxhighlight>
{{out}}
<pre>
GordonCharlton
1,462

edits

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