Greedy algorithm for Egyptian fractions: Difference between revisions
Greedy algorithm for Egyptian fractions (view source)
Revision as of 16:12, 12 December 2023
, 5 months agoAdded link to numberphile video
(→{{header|Python}}: Added a functionally composed version.) |
(Added link to numberphile video) |
||
| (41 intermediate revisions by 14 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>
=={{header|ALGOL 68}}==
{{works with|ALGOL 68G|Any - tested with release 2.8.3.win32}}
Based on the VB.NET sample.<br>
Uses Algol 68G's LONG LONG INT for large integers.
<syntaxhighlight 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:
IF b = 0 THEN
IF a < 0 THEN
- a
ELSE
a
FI
ELSE
gcd( b, a MOD b )
FI ; # gcd #
MODE RATIONAL = STRUCT( LONG LONG INT num, den );
MODE LISTOFRATIONAL = STRUCT( RATIONAL element, REF LISTOFRATIONAL next );
REF LISTOFRATIONAL nil list of rational = NIL;
OP TOSTRING = ( INT a )STRING: whole( a, 0 );
OP TOSTRING = ( LONG INT a )STRING: whole( a, 0 );
OP TOSTRING = ( LONG LONG INT a )STRING: whole( a, 0 );
OP TOSTRING = ( RATIONAL a )STRING:
IF den OF a = 1
THEN TOSTRING num OF a
ELSE TOSTRING num OF a + "/" + TOSTRING den OF a
FI ; # TOSTRING #
OP TOSTRING = ( REF LISTOFRATIONAL lr )STRING:
BEGIN
REF LISTOFRATIONAL p := lr;
STRING result := "[";
WHILE p ISNT nil list of rational DO
result +:= TOSTRING element OF p;
IF next OF p IS nil list of rational THEN
p := NIL
ELSE
p := next OF p;
result +:= " + "
FI
OD;
result + "]"
END ; # TOSTRING #
OP CEIL = ( LONG LONG REAL v )LONG LONG INT:
IF LONG LONG INT result := ENTIER v;
ABS v > ABS result
THEN result + 1
ELSE result
FI ; # CEIL #
OP EGYPTIAN = ( RATIONAL rp )REF LISTOFRATIONAL:
IF RATIONAL r := rp;
num OF r = 0 OR num OF r = 1
THEN HEAP LISTOFRATIONAL := ( r, nil list of rational )
ELSE
REF LISTOFRATIONAL result := nil list of rational;
REF LISTOFRATIONAL end result := nil list of rational;
PROC add = ( RATIONAL r )VOID:
IF end result IS nil list of rational THEN
result := HEAP LISTOFRATIONAL := ( r, nil list of rational );
end result := result
ELSE
next OF end result := HEAP LISTOFRATIONAL := ( r, nil list of rational );
end result := next OF end result
FI ; # add #
IF num OF r > den OF r THEN
add( RATIONAL( num OF r OVER den OF r, 1 ) );
r := ( num OF r MOD den OF r, den OF r )
FI;
PROC mod func = ( LONG LONG INT m, n )LONG LONG INT: ( ( m MOD n ) + n ) MOD n;
WHILE num OF r /= 0 DO
LONG LONG INT q = CEIL( den OF r / num OF r );
add( RATIONAL( 1, q ) );
r := RATIONAL( mod func( - ( den OF r ), num OF r ), ( den OF r ) * q )
OD;
result
FI ; # EGYPTIAN #
BEGIN # task test cases #
[]RATIONAL test cases = ( RATIONAL( 43, 48 ), RATIONAL( 5, 121 ), RATIONAL( 2014, 59 ) );
FOR r pos FROM LWB test cases TO UPB test cases DO
print( ( TOSTRING test cases[ r pos ], " -> ", TOSTRING EGYPTIAN test cases[ r pos ], newline ) )
OD;
# find the fractions with the most terms and the largest denominator #
print( ( "For rationals with numerator and denominator in 1..99:", newline ) );
RATIONAL largest denominator := ( 0, 1 );
REF LISTOFRATIONAL max denominator list := nil list of rational;
LONG LONG INT max denominator := 0;
RATIONAL most terms := ( 0, 1 );
REF LISTOFRATIONAL most terms list := nil list of rational;
INT max terms := 0;
FOR num TO 99 DO
FOR den TO 99 DO
RATIONAL r = RATIONAL( num, den );
REF LISTOFRATIONAL e := EGYPTIAN r;
REF LISTOFRATIONAL p := e;
INT terms := 0;
WHILE p ISNT nil list of rational DO
terms +:= 1;
IF den OF element OF p > max denominator THEN
largest denominator := r;
max denominator := den OF element OF p;
max denominator list := e
FI;
p := next OF p
OD;
IF terms > max terms THEN
most terms := r;
max terms := terms;
most terms list := e
FI
OD
OD;
print( ( " ", TOSTRING most terms, " has the most terms: ", TOSTRING max terms, newline
, " ", TOSTRING most terms list, newline
)
);
print( ( " ", TOSTRING largest denominator, " has the largest denominator:", newline
, " ", TOSTRING max denominator list, newline
)
)
END
END</syntaxhighlight>
{{out}}
<pre>
43/48 -> [1/2 + 1/3 + 1/16]
5/121 -> [1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1527612795642093418846225]
2014/59 -> [34 + 1/8 + 1/95 + 1/14947 + 1/670223480]
For rationals with numerator and denominator in 1..99:
97/53 has the most terms: 9
[1 + 1/2 + 1/4 + 1/13 + 1/307 + 1/120871 + 1/20453597227 + 1/697249399186783218655 + 1/1458470173998990524806872692984177836808420]
8/97 has the largest denominator:
[1/13 + 1/181 + 1/38041 + 1/1736503177 + 1/3769304102927363485 + 1/18943537893793408504192074528154430149 + 1/538286441900380211365817285104907086347439746130226973253778132494225813153 + 1/579504587067542801713103191859918608251030291952195423583529357653899418686342360361798689053273749372615043661810228371898539583862011424993909789665]
</pre>
=={{header|C}}==
Output has limited accuracy as noted by comments. The problem requires bigint support to be completely accurate.
<syntaxhighlight lang="c">#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
typedef int64_t integer;
struct Pair {
integer md;
int tc;
};
integer mod(integer x, integer y) {
return ((x % y) + y) % y;
}
integer gcd(integer a, integer b) {
if (0 == a) return b;
if (0 == b) return a;
if (a == b) return a;
if (a > b) return gcd(a - b, b);
return gcd(a, b - a);
}
void write0(bool show, char *str) {
if (show) {
printf(str);
}
}
void write1(bool show, char *format, integer a) {
if (show) {
printf(format, a);
}
}
void write2(bool show, char *format, integer a, integer b) {
if (show) {
printf(format, a, b);
}
}
struct Pair egyptian(integer x, integer y, bool show) {
struct Pair ret;
integer acc = 0;
bool first = true;
ret.tc = 0;
ret.md = 0;
write2(show, "Egyptian fraction for %lld/%lld: ", x, y);
while (x > 0) {
integer z = (y + x - 1) / x;
if (z == 1) {
acc++;
} else {
if (acc > 0) {
write1(show, "%lld + ", acc);
first = false;
acc = 0;
ret.tc++;
} else if (first) {
first = false;
} else {
write0(show, " + ");
}
if (z > ret.md) {
ret.md = z;
}
write1(show, "1/%lld", z);
ret.tc++;
}
x = mod(-y, x);
y = y * z;
}
if (acc > 0) {
write1(show, "%lld", acc);
ret.tc++;
}
write0(show, "\n");
return ret;
}
int main() {
struct Pair p;
integer nm = 0, dm = 0, dmn = 0, dmd = 0, den = 0;;
int tm, i, j;
egyptian(43, 48, true);
egyptian(5, 121, true); // final term cannot be represented correctly
egyptian(2014, 59, true);
tm = 0;
for (i = 1; i < 100; i++) {
for (j = 1; j < 100; j++) {
p = egyptian(i, j, false);
if (p.tc > tm) {
tm = p.tc;
nm = i;
dm = j;
}
if (p.md > den) {
den = p.md;
dmn = i;
dmd = j;
}
}
}
printf("Term max is %lld/%lld with %d terms.\n", nm, dm, tm); // term max is correct
printf("Denominator max is %lld/%lld\n", dmn, dmd); // denominator max is not correct
egyptian(dmn, dmd, true); // enough digits cannot be represented without bigint
return 0;
}</syntaxhighlight>
{{out}}
<pre>Egyptian fraction for 43/48: 1/2 + 1/3 + 1/16
Egyptian fraction for 5/121: 1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1025410058030422033
Egyptian fraction for 2014/59: 34 + 1/8 + 1/95 + 1/14947 + 1/670223480
Term max is 97/53 with 9 terms.
Denominator max is 69/97
Egyptian fraction for 69/97: 1/2 + 1/5 + 1/89 + 1/9593 + 1/118309099 + 1/32659766662805104 + 1/2591418766870639376</pre>
=={{header|C sharp|C#}}==
{{trans|Visual Basic .NET}}
<syntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
namespace EgyptianFractions {
class Program {
class Rational : IComparable<Rational>, IComparable<int> {
public BigInteger Num { get; }
public BigInteger Den { get; }
public Rational(BigInteger n, BigInteger d) {
var c = Gcd(n, d);
Num = n / c;
Den = d / c;
if (Den < 0) {
Num = -Num;
Den = -Den;
}
}
public Rational(BigInteger n) {
Num = n;
Den = 1;
}
public override string ToString() {
if (Den == 1) {
return Num.ToString();
} else {
return string.Format("{0}/{1}", Num, Den);
}
}
public Rational Add(Rational rhs) {
return new Rational(Num * rhs.Den + rhs.Num * Den, Den * rhs.Den);
}
public Rational Sub(Rational rhs) {
return new Rational(Num * rhs.Den - rhs.Num * Den, Den * rhs.Den);
}
public int CompareTo(Rational rhs) {
var ad = Num * rhs.Den;
var bc = Den * rhs.Num;
return ad.CompareTo(bc);
}
public int CompareTo(int rhs) {
var ad = Num * rhs;
var bc = Den * rhs;
return ad.CompareTo(bc);
}
}
static BigInteger Gcd(BigInteger a, BigInteger b) {
if (b == 0) {
if (a < 0) {
return -a;
} else {
return a;
}
} else {
return Gcd(b, a % b);
}
}
static List<Rational> Egyptian(Rational r) {
List<Rational> result = new List<Rational>();
if (r.CompareTo(1) >= 0) {
if (r.Den == 1) {
result.Add(r);
result.Add(new Rational(0));
return result;
}
result.Add(new Rational(r.Num / r.Den));
r = r.Sub(result[0]);
}
BigInteger modFunc(BigInteger m, BigInteger n) {
return ((m % n) + n) % n;
}
while (r.Num != 1) {
var q = (r.Den + r.Num - 1) / r.Num;
result.Add(new Rational(1, q));
r = new Rational(modFunc(-r.Den, r.Num), r.Den * q);
}
result.Add(r);
return result;
}
static string FormatList<T>(IEnumerable<T> col) {
StringBuilder sb = new StringBuilder();
var iter = col.GetEnumerator();
sb.Append('[');
if (iter.MoveNext()) {
sb.Append(iter.Current);
}
while (iter.MoveNext()) {
sb.AppendFormat(", {0}", iter.Current);
}
sb.Append(']');
return sb.ToString();
}
static void Main() {
List<Rational> rs = new List<Rational> {
new Rational(43, 48),
new Rational(5, 121),
new Rational(2014, 59)
};
foreach (var r in rs) {
Console.WriteLine("{0} => {1}", r, FormatList(Egyptian(r)));
}
var lenMax = Tuple.Create(0UL, new Rational(0));
var denomMax = Tuple.Create(BigInteger.Zero, new Rational(0));
var query = (from i in Enumerable.Range(1, 100)
from j in Enumerable.Range(1, 100)
select new Rational(i, j))
.Distinct()
.ToList();
foreach (var r in query) {
var e = Egyptian(r);
ulong eLen = (ulong) e.Count;
var eDenom = e.Last().Den;
if (eLen > lenMax.Item1) {
lenMax = Tuple.Create(eLen, r);
}
if (eDenom > denomMax.Item1) {
denomMax = Tuple.Create(eDenom, r);
}
}
Console.WriteLine("Term max is {0} with {1} terms", lenMax.Item2, lenMax.Item1);
var dStr = denomMax.Item1.ToString();
Console.WriteLine("Denominator max is {0} with {1} digits {2}...{3}", denomMax.Item2, dStr.Length, dStr.Substring(0, 5), dStr.Substring(dStr.Length - 5, 5));
}
}
}</syntaxhighlight>
{{out}}
<pre>43/48 => [1/2, 1/3, 1/16]
5/121 => [1/25, 1/757, 1/763309, 1/873960180913, 1/1527612795642093418846225]
2014/59 => [34, 1/8, 1/95, 1/14947, 1/670223480]
Term max is 97/53 with 9 terms
Denominator max is 8/97 with 150 digits 57950...89665</pre>
=={{header|C++}}==
{{libheader|Boost}}
The C++ standard library does not have a "big integer" type, so this solution uses the Boost library.
<syntaxhighlight lang="cpp">#include <boost/multiprecision/cpp_int.hpp>
#include <iostream>
#include <optional>
#include <sstream>
#include <string>
#include <vector>
typedef boost::multiprecision::cpp_int integer;
struct fraction {
fraction(const integer& n, const integer& d)
: numerator(n), denominator(d) {}
integer numerator;
integer denominator;
};
integer mod(const integer& x, const integer& y) { return ((x % y) + y) % y; }
size_t count_digits(const integer& i) {
std::ostringstream os;
os << i;
return os.str().length();
}
std::string to_string(const integer& i) {
const int max_digits = 20;
std::ostringstream os;
os << i;
std::string s = os.str();
if (s.length() > max_digits)
s.replace(max_digits / 2, s.length() - max_digits, "...");
return s;
}
std::ostream& operator<<(std::ostream& out, const fraction& f) {
return out << to_string(f.numerator) << '/' << to_string(f.denominator);
}
void egyptian(const fraction& f, std::vector<fraction>& result) {
result.clear();
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);
y = y * z;
}
}
void print_egyptian(const std::vector<fraction>& result) {
if (result.empty())
return;
auto i = result.begin();
std::cout << *i++;
for (; i != result.end(); ++i)
std::cout << " + " << *i;
std::cout << '\n';
}
void print_egyptian(const fraction& f) {
std::cout << "Egyptian fraction for " << f << ": ";
integer x = f.numerator, y = f.denominator;
if (x > y) {
std::cout << "[" << x / y << "] ";
x = x % y;
}
std::vector<fraction> result;
egyptian(fraction(x, y), result);
print_egyptian(result);
std::cout << '\n';
}
void show_max_terms_and_max_denominator(const integer& limit) {
size_t max_terms = 0;
std::optional<fraction> max_terms_fraction, max_denominator_fraction;
std::vector<fraction> max_terms_result;
integer max_denominator = 0;
std::vector<fraction> max_denominator_result;
std::vector<fraction> result;
for (integer b = 2; b < limit; ++b) {
for (integer a = 1; a < b; ++a) {
fraction f(a, b);
egyptian(f, result);
if (result.size() > max_terms) {
max_terms = result.size();
max_terms_result = result;
max_terms_fraction = f;
}
const integer& denominator = result.back().denominator;
if (denominator > max_denominator) {
max_denominator = denominator;
max_denominator_result = result;
max_denominator_fraction = f;
}
}
}
std::cout
<< "Proper fractions with most terms and largest denominator, limit = "
<< 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_fraction.value() << " = ";
print_egyptian(max_denominator_result);
}
int main() {
print_egyptian(fraction(43, 48));
print_egyptian(fraction(5, 121));
print_egyptian(fraction(2014, 59));
show_max_terms_and_max_denominator(100);
show_max_terms_and_max_denominator(1000);
return 0;
}</syntaxhighlight>
{{out}}
<pre>
Egyptian fraction for 43/48: 1/2 + 1/3 + 1/16
Egyptian fraction for 5/121: 1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1527612795...3418846225
Egyptian fraction for 2014/59: [34] 1/8 + 1/95 + 1/14947 + 1/670223480
Proper fractions with most terms and largest denominator, limit = 100:
Most terms (8): 44/53 = 1/2 + 1/4 + 1/13 + 1/307 + 1/120871 + 1/20453597227 + 1/6972493991...6783218655 + 1/1458470173...7836808420
Largest denominator (150 digits): 8/97 = 1/13 + 1/181 + 1/38041 + 1/1736503177 + 1/3769304102927363485 + 1/1894353789...8154430149 + 1/5382864419...4225813153 + 1/5795045870...3909789665
Proper fractions with most terms and largest denominator, limit = 1000:
Most terms (13): 641/796 = 1/2 + 1/4 + 1/19 + 1/379 + 1/159223 + 1/28520799973 + 1/9296411783...1338400861 + 1/1008271507...4174730681 + 1/1219933718...8484537833 + 1/1860297848...1025882029 + 1/4614277444...8874327093 + 1/3193733450...1456418881 + 1/2039986670...2410165441
Largest denominator (2847 digits): 36/457 = 1/13 + 1/541 + 1/321409 + 1/114781617793 + 1/1482167225...0844346913 + 1/2510651068...4290086881 + 1/7353930250...3326272641 + 1/6489634815...7391865217 + 1/5264420004...5476206145 + 1/3695215730...1238141889 + 1/2048192894...4706590593 + 1/8390188268...5525592705
</pre>
=={{header|Common Lisp}}==
<
(let* ((a (/ x y)))
(cond
Line 62 ⟶ 616:
#'>
:key #'cdr)))
</syntaxhighlight>
{{out}}
Line 91 ⟶ 645:
Assuming the Python entry is correct, this code is equivalent. This requires the D module of the Arithmetic/Rational task.
{{trans|Python}}
<
arithmetic_rational: Rat = Rational;
Line 138 ⟶ 692:
writefln("Denominator max is %s with %d digits %s...%s",
denomMax[1], dStr.length, dStr[0 .. 5], dStr[$ - 5 .. $]);
}</
{{out}}
<pre>43/48 => 1/2 1/3 1/16
Line 146 ⟶ 700:
Denominator max is 8/97 with 150 digits 57950...89665</pre>
=={{header|Erlang}}==
<syntaxhighlight lang="erlang">-module(egypt).
-import(lists, [reverse/1, seq/2]).
-export([frac/2, show/2, rosetta/0]).
rosetta() ->
Fractions = [{N, D, second(frac(N, D))} || N <- seq(2,99), D <- seq(N+1, 99)],
{Longest, A1, B1} = findmax(fun length/1, Fractions),
io:format("~b/~b has ~b terms.~n", [A1, B1, Longest]),
{Largest, A2, B2} = findmax(fun (L) -> hd(reverse(L)) end, Fractions),
io:format("~b/~b has a really long denominator. (~b)~n", [A2, B2, Largest]).
second({_, B}) -> B.
findmax(Fn, L) -> findmax(Fn, L, 0, 0, 0).
findmax(_, [], M, A, B) -> {M, A, B};
findmax(Fn, [{A,B,Frac}|Fracs], M, A0, B0) ->
Val = Fn(Frac),
case Val > M of
true -> findmax(Fn, Fracs, Val, A, B);
false -> findmax(Fn, Fracs, M, A0, B0)
end.
show(A, B) ->
{W, R} = frac(A, B),
case W of
0 -> ok;
_ -> io:format("[~b] ", [W])
end,
case R of
[] -> ok;
[D0|Ds] ->
io:format("1/~b ", [D0]),
[io:format("+ 1/~b ", [D]) || D <- Ds],
ok
end.
frac(A, B) ->
{A div B, reverse(proper(A rem B, B, []))}.
proper(0, _, L) -> L;
proper(1, Y, L) -> [Y|L];
proper(X, Y, L) ->
D = ceildiv(Y, X),
X2 = mod(-Y, X),
Y2 = Y*ceildiv(Y, X),
proper(X2, Y2, [D|L]).
ceildiv(A, B) ->
Q = A div B,
case A rem B of
0 -> Q;
_ -> Q+1
end.
mod(A, M) ->
B = A rem M,
if
B < 0 -> B + M;
true -> B
end.
</syntaxhighlight>
{{out}}
<pre>
129> egypt:show(43,48).
1/2 + 1/3 + 1/16 ok
130> egypt:show(5,121).
1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1527612795642093418846225 ok
131> egypt:show(2014,59).
[34] 1/8 + 1/95 + 1/14947 + 1/670223480 ok
132> egypt:rosetta().
8/97 has 8 terms.
8/97 has a really long denominator. (579504587067542801713103191859918608251030291952195423583529357653899418686342360361798689053273749372615043661810228371898539583862011424993909789665)
ok
</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}}==
<
math.functions math.ranges sequences ;
IN: rosetta-code.egyptian-fractions
Line 193 ⟶ 849:
: egyptian-fractions-demo ( -- ) part1 part2 ;
MAIN: egyptian-fractions-demo</
{{out}}
<pre>
Line 205 ⟶ 861:
=={{header|FreeBASIC}}==
{{libheader|GMP}}
<
' compile with: fbc -s console
Line 373 ⟶ 1,029:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre>43/48 = 1/2 + 1/3 + 1/16
Line 389 ⟶ 1,045:
Largest number of terms is 13 for 641/796, 529/914
Largest size for denominator is 2847 for 36/457, 529/914</pre>
=={{header|Frink}}==
<syntaxhighlight lang="frink">
frac[p, q] :=
{
a = makeArray[[0]]
if p > q
{
a.push[floor[p / q]]
p = p mod q
}
while p > 1
{
d = ceil[q / p]
a.push[1/d]
[p, q] = [-q mod p, d q]
}
if p == 1
a.push[1/q]
a
}
showApproximations[false]
egypt[p, q] := join[" + ", frac[p, q]]
rosetta[] :=
{
lMax = 0
longest = 0
dMax = 0
biggest = 0
for n = 1 to 99
for d = n+1 to 99
{
egypt = frac[n, d]
if length[egypt] > lMax
{
lMax = length[egypt]
longest = n/d
}
d2 = denominator[last[egypt, 1]@0]
if d2 > dMax
{
dMax = d2
biggest = n/d
}
}
println["The fraction with the largest number of terms is $longest"]
println["The fraction with the largest denominator is $biggest"]
}
</syntaxhighlight>
{{Out}}
<pre>
rosetta[]
The fraction with the largest number of terms is 8/97
The fraction with the largest denominator is 8/97
egypt[43,48]
1/2 + 1/3 + 1/16
egypt[5,121]
1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1527612795642093418846225
egypt[2014,59]
34 + 1/8 + 1/95 + 1/14947 + 1/670223480
</pre>
=={{header|Fōrmulæ}}==
{{FormulaeEntry|page=https://formulae.org/?script=examples/Egyptian_fractions}}
'''Solution'''
[[File:Fōrmulæ - Egyptian fractions 01.png]]
'''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.
<
import (
Line 529 ⟶ 1,293:
fmt.Println(" fraction(s) with this denominator :", maxDenFracs)
}
}</
{{out}}
Line 551 ⟶ 1,315:
=={{header|Haskell}}==
<
egyptianFraction :: Integral a => Ratio a -> [Ratio a]
Line 563 ⟶ 1,327:
x = numerator n
y = denominator n
r = y `div` x + 1</
'''Testing''':
<
λ> quickCheck (\n -> n == (sum $ egyptianFraction n))
+++ OK, passed 100 tests.</
'''Tasks''':
<
import Data.Ord (comparing)
Line 593 ⟶ 1,357:
| a <- [1 .. n]
, b <- [1 .. n]
, a < b ]</
<
43 % 48 = 1 % 2 + 1 % 3 + 1 % 16
5 % 121 = 1 % 25 + 1 % 757 + 1 % 763309 + 1 % 873960180913 + 1 % 1527612795642093418846225
Line 607 ⟶ 1,371:
λ> task22 999
(529 % 914, 839018826833450186636781520007011999269820404906753180244759299287837378895397605613261469995626498719289835112392530430840514102146998625666594756995273418015600023494049208108894185781774002683063204252356172520941088783702738286944210460710059319691268110283467445381026653628599765684739105388642310044785844902157076919003735231543781785073393176144167688252446541416466418608465458502997971425428342769433127784560570193376772878336217849260872114137931351960543608384244009505664253173875705234889570853924105640193619301332776989688248555027054395237907581951261868280899150574360164800187964167274323078311078867593844043149124596271281252530924719121766925749760855109100066731841478262812686642693395896229983745226277793055820609058348269152190083695704685769622011655159174272326647342695589818127126303038171968768650476413027459205291075571637957597356820188031655122749743652301268394542123970892422944335857917641636041892192547135178153602038877677614358281581103685526041329841496863410305888255234495015115912388514981113593387572720476744188169200130515719608747338810136728267784013352396910979904545913458536243327311977805126410065576961237640824852114328884086581542091492600312838425666927627674227053793897767395465326589843035773944346372949759909905561209334216847158156644884281300512699910530092870919061876615770708519243818676366245477462042294267674677954783726990349386117468071932874021023714524610740225814235147693954027910741673103980749749728106483987721602738673173009362802337092908847797499475895347112889339502928407808058670297722175686638678788738689803945574002805677250463286479363670076942509109589495377221095405979217163821481666646160815221224686562530536116613645305335922819524037829878961518170177968768364853399057357772141655622381280196908637031556436461404285930426436983658106288733881761514992109680298995922754466040011586713812553117621857109517258943846004179432521131844156242428351270188803919554398620084668514054504414062276012292497375238210886595006249453460414790147611422121782194848803348777061816460876697945418158442269512987729152441940326466631610424906158237288218706447963113019239557885486647314085357651895226117364760315394354624547919209138539180807829672545924239541758108877100331729470119526373928796447673951888289511964811633025369821156695934557103429921063387965046715070102916811976552584464153981214277622597308113449320462341683055200576571910241686615924531368198770946893858410058348221985603151428153382461711196734214085852523778422630907646235900752317571022131569421231196329080023952364788544301495422061066036911772385739659997665503832444529713544286955548310166168837889046149061296461059432238621602179724809510024772127497080258401694929973105184832214622785679651550368465524821062859837409907538269572622296774545103747438431266995525592705)
</syntaxhighlight>
=={{header|J}}==
'''Solution''':<
r2ef =: (<(<0);0) { ((] , -) >:@:<.&.%)^:((~:<.)@:%)@:{:^:a:</
'''Examples''' (''required''):<
+-------+--------------------------------------------------------------+
|43r48 |1r2 1r3 1r16 |
Line 620 ⟶ 1,384:
+-------+--------------------------------------------------------------+
|2014r59|34 1r8 1r95 1r14947 1r670223480 |
+-------+--------------------------------------------------------------+</
'''Examples''' (''extended''):<
EF2 =: ef :: _1:&.> (</~ * %/~) i. 10^2x
Line 687 ⟶ 1,451:
52971354428695554831016616883788904614906129646105943223862160217972480951002477
21274970802584016949299731051848322146227856796515503684655248210628598374099075
38269572622296774545103747438431266995525592705 </
=={{header|Java}}==
{{trans|Kotlin}}
{{works with|Java|9}}
<
import java.math.BigInteger;
import java.math.MathContext;
Line 902 ⟶ 1,666:
}
}
}</
{{out}}
<pre>43/48 -> 1/2 + 1/3 + 1/16
Line 923 ⟶ 1,687:
{{works with|Julia|0.6}}
<
int::T
frac::NTuple{N,Rational{T}} where N
Line 988 ⟶ 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)</
{{out}}
Line 1,024 ⟶ 1,788:
=={{header|Kotlin}}==
As the JDK lacks a fraction or rational class, I've included a basic one in the program.
<
import java.math.BigInteger
Line 1,191 ⟶ 1,955:
println(" fraction(s) with this denominator : $maxDenFracs")
}
}</
{{out}}
Line 1,212 ⟶ 1,976:
</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<
frac[n_] :=
frac[n] =
Line 1,234 ⟶ 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]]]];</
{{out}}
<pre>1/2 + 1/3 + 1/16 = 43/48
Line 1,246 ⟶ 2,010:
=={{header|Microsoft Small Basic}}==
Small Basic but large (not huge) integers.
<
xx=2014
yy=59
Line 1,299 ⟶ 2,063:
EndWhile
ret=wx
EndSub </
{{out}}
43/48=1/2+1/3
5/121=1/25+1/757+1/763309+1/873960180913+1/1527612795642093418846225
2014/59=(34)+1/8+1/95+1/14947+1/670223480
=={{header|Nim}}==
{{trans|Go}}
{{libheader|bignum}}
<syntaxhighlight lang="nim">import strformat, strutils
import bignum
let
Zero = newInt(0)
One = newInt(1)
#---------------------------------------------------------------------------------------------------
proc toEgyptianrecursive(rat: Rat; fracs: seq[Rat]): seq[Rat] =
if rat.isZero: return fracs
let iquo = cdiv(rat.denom, rat.num)
let rquo = newRat(1, iquo)
result = fracs & rquo
let num2 = cmod(-rat.denom, rat.num)
if num2 < Zero:
num2 += rat.num
let denom2 = rat.denom * iquo
let f = newRat(num2, denom2)
if f.num == One:
result.add(f)
else:
result = f.toEgyptianrecursive(result)
#---------------------------------------------------------------------------------------------------
proc toEgyptian(rat: Rat): seq[Rat] =
if rat.num.isZero: return @[rat]
if abs(rat.num) >= rat.denom:
let iquo = rat.num div rat.denom
let rquo = newRat(iquo, 1)
let rrem = rat - rquo
result = rrem.toEgyptianrecursive(@[rquo])
else:
result = rat.toEgyptianrecursive(@[])
#———————————————————————————————————————————————————————————————————————————————————————————————————
for frac in [newRat(43, 48), newRat(5, 121), newRat(2014, 59)]:
let list = frac.toEgyptian()
if list[0].denom == One:
let first = fmt"[{list[0].num}]"
let rest = list[1..^1].join(" + ")
echo fmt"{frac} -> {first} + {rest}"
else:
let all = list.join(" + ")
echo fmt"{frac} -> {all}"
for r in [98, 998]:
if r == 98:
echo "\nFor proper fractions with 1 or 2 digits:"
else:
echo "\nFor proper fractions with 1, 2 or 3 digits:"
var maxSize = 0
var maxSizeFracs: seq[Rat]
var maxDen = Zero
var maxDenFracs: seq[Rat]
var sieve = newSeq[seq[bool]](r + 1) # To eliminate duplicates.
for item in sieve.mitems: item.setLen(r + 2)
for i in 1..r:
for j in (i + 1)..(r + 1):
if sieve[i][j]: continue
let f = newRat(i, j)
let list = f.toEgyptian()
let listSize = list.len
if listSize > maxSize:
maxSize = listSize
maxSizeFracs.setLen(0)
maxSizeFracs.add(f)
elif listSize == maxSize:
maxSizeFracs.add(f)
let listDen = list[^1].denom()
if listDen > maxDen:
maxDen = listDen
maxDenFracs.setLen(0)
maxDenFracs.add(f)
elif listDen == maxDen:
maxDenFracs.add(f)
if i < r div 2:
var k = 2
while j * k <= r + 1:
sieve[i * k][j * k] = true
inc k
echo fmt" largest number of items = {maxSize}"
echo fmt" fraction(s) with this number : {maxSizeFracs.join("", "")}"
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("", "")}"</syntaxhighlight>
{{out}}
<pre>43/48 -> 1/2 + 1/3 + 1/16
5/121 -> 1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1527612795642093418846225
2014/59 -> [34] + 1/8 + 1/95 + 1/14947 + 1/670223480
For proper fractions with 1 or 2 digits:
largest number of items = 8
fraction(s) with this number : 8/97, 44/53
largest denominator = 150 digits, 57950458706754280171...62011424993909789665
fraction(s) with this denominator : 8/97
For proper fractions with 1, 2 or 3 digits:
largest number of items = 13
fraction(s) with this number : 529/914, 641/796
largest denominator = 2847 digits, 83901882683345018663...38431266995525592705
fraction(s) with this denominator : 36/457, 529/914</pre>
=={{header|PARI/GP}}==
<
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 1,314 ⟶ 2,197:
best(99)
best(999)
</syntaxhighlight>
{{out}}
<pre>43/48 = [0; 2, 3, 16]
Line 1,328 ⟶ 2,211:
Most terms is 529/914 with 13
Biggest denominator is 36/457 with 839...705</pre>
=={{header|Perl}}==
<
use warnings;
use bigint;
Line 1,364 ⟶ 2,248:
printf "\nEgyptian Fraction Representation of " . $nrI . "/" . $deI . " is: \n\n";
isEgyption($nrI,$deI);
</syntaxhighlight>
{{out}}
<pre>
Line 1,370 ⟶ 2,254:
34 + 1/8 + 1/95 + 1/14947 + 1/670223480
</pre>
=={{header|Phix}}==
{{trans|tcl}}
{{libheader|
The sieve copied from Go
<!--<syntaxhighlight lang="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>
<span style="color: #008080;">function</span> <span style="color: #000000;">egyptian</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">num</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">denom</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">mpz</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">num</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #000000;">denom</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">result</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{}</span>
<span style="color: #008080;">while</span> <span style="color: #7060A8;">mpz_cmp_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)!=</span><span style="color: #000000;">0</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">mpz_cdiv_q</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">result</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">result</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"1/"</span><span style="color: #0000FF;">&</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">))</span>
<span style="color: #7060A8;">mpz_neg</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_mod</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_neg</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">mpz_mul</span><span style="color: #0000FF;">(</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">,</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_free</span><span style="color: #0000FF;">({</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">result</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">efrac</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">num</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">denom</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">fraction</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%d/%d"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">num</span><span style="color: #0000FF;">,</span><span style="color: #000000;">denom</span><span style="color: #0000FF;">}),</span>
<span style="color: #000000;">prefix</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">num</span><span style="color: #0000FF;">>=</span><span style="color: #000000;">denom</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">whole</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">floor</span><span style="color: #0000FF;">(</span><span style="color: #000000;">num</span><span style="color: #0000FF;">/</span><span style="color: #000000;">denom</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">num</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">whole</span><span style="color: #0000FF;">*</span><span style="color: #000000;">denom</span>
<span style="color: #000000;">prefix</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"[%d] + "</span><span style="color: #0000FF;">,</span><span style="color: #000000;">whole</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">e</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #000000;">egyptian</span><span style="color: #0000FF;">(</span><span style="color: #000000;">num</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">denom</span><span style="color: #0000FF;">),</span><span style="color: #008000;">" + "</span><span style="color: #0000FF;">)</span>
<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;">"%s -> %s%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">fraction</span><span style="color: #0000FF;">,</span><span style="color: #000000;">prefix</span><span style="color: #0000FF;">,</span><span style="color: #000000;">e</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #000000;">efrac</span><span style="color: #0000FF;">(</span><span style="color: #000000;">43</span><span style="color: #0000FF;">,</span><span style="color: #000000;">48</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">efrac</span><span style="color: #0000FF;">(</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span><span style="color: #000000;">121</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">efrac</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2014</span><span style="color: #0000FF;">,</span><span style="color: #000000;">59</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">maxt</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">maxd</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">maxts</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">maxds</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">maxda</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">=</span><span style="color: #000000;">98</span> <span style="color: #008080;">to</span> <span style="color: #000000;">998</span> <span style="color: #008080;">by</span> <span style="color: #000000;">900</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- (iterates just twice!)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">sieve</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #004600;">false</span><span style="color: #0000FF;">,</span><span style="color: #000000;">r</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">),</span><span style="color: #000000;">r</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- to eliminate duplicates</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">r</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">=</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">sieve</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">][</span><span style="color: #000000;">d</span><span style="color: #0000FF;">]=</span><span style="color: #004600;">false</span> <span style="color: #008080;">then</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">term</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%d/%d"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">})</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">terms</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">egyptian</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">d</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">nterms</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">terms</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">nterms</span><span style="color: #0000FF;">></span><span style="color: #000000;">maxt</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">maxt</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nterms</span>
<span style="color: #000000;">maxts</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">term</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">nterms</span><span style="color: #0000FF;">=</span><span style="color: #000000;">maxt</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">maxts</span> <span style="color: #0000FF;">&=</span> <span style="color: #008000;">", "</span> <span style="color: #0000FF;">&</span> <span style="color: #000000;">term</span>
<span style="color: #008080;">end</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">mlen</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">terms</span><span style="color: #0000FF;">[$])-</span><span style="color: #000000;">2</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">mlen</span><span style="color: #0000FF;">></span><span style="color: #000000;">maxd</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">maxd</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mlen</span>
<span style="color: #000000;">maxds</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">term</span>
<span style="color: #000000;">maxda</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">terms</span><span style="color: #0000FF;">[$]</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">mlen</span><span style="color: #0000FF;">=</span><span style="color: #000000;">maxd</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">maxds</span> <span style="color: #0000FF;">&=</span> <span style="color: #008000;">", "</span> <span style="color: #0000FF;">&</span> <span style="color: #000000;">term</span>
<span style="color:
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><</span><span style="color: #000000;">r</span><span style="color: #0000FF;">/</span><span style="color: #000000;">2</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span> <span style="color: #008080;">to</span> <span style="color: #000000;">9999</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">*</span><span style="color: #000000;">k</span> <span style="color: #0000FF;">></span> <span style="color: #000000;">r</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">sieve</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">*</span><span style="color: #000000;">k</span><span style="color: #0000FF;">][</span><span style="color: #000000;">d</span><span style="color: #0000FF;">*</span><span style="color: #000000;">k</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<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;">"\nfor proper fractions with 1 to %d digits\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">sprint</span><span style="color: #0000FF;">(</span><span style="color: #000000;">r</span><span style="color: #0000FF;">))})</span>
<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 number of terms is %d for %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">maxt</span><span style="color: #0000FF;">,</span><span style="color: #000000;">maxts</span><span style="color: #0000FF;">})</span>
<span style="color: #000000;">maxda</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">maxda</span><span style="color: #0000FF;">[</span><span style="color: #000000;">3</span><span style="color: #0000FF;">..$]</span> <span style="color: #000080;font-style:italic;">-- (strip the "1/")</span>
<span style="color: #000000;">maxda</span><span style="color: #0000FF;">[</span><span style="color: #000000;">6</span><span style="color: #0000FF;">..-</span><span style="color: #000000;">6</span><span style="color: #0000FF;">]=</span><span style="color: #008000;">"..."</span> <span style="color: #000080;font-style:italic;">-- (show only first/last 5 digits)</span>
<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>
<!--</syntaxhighlight>-->
{{out}}
<pre>
43/48 -> 1/2 + 1/3 + 1/16
5/121 -> 1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1527612795642093418846225
for proper fractions with 1 to 2 digits
Line 1,519 ⟶ 2,352:
Largest number of terms is 13 for 529/914, 641/796
Largest size for denominator is 2847 digits (83901...92705) for 36/457, 529/914
</pre>
=={{header|Prolog}}==
{{works with|SWI Prolog}}
<syntaxhighlight lang="prolog">count_digits(Number, Count):-
atom_number(A, Number),
atom_length(A, Count).
integer_to_atom(Number, Atom):-
atom_number(A, Number),
atom_length(A, Count),
(Count =< 20 ->
Atom = A
;
sub_atom(A, 0, 10, _, A1),
P is Count - 10,
sub_atom(A, P, 10, _, A2),
atom_concat(A1, '...', A3),
atom_concat(A3, A2, Atom)
).
egyptian(0, _, []):- !.
egyptian(X, Y, [Z|E]):-
Z is (Y + X - 1)//X,
X1 is -Y mod X,
Y1 is Y * Z,
egyptian(X1, Y1, E).
print_egyptian([]):- !.
print_egyptian([N|List]):-
integer_to_atom(N, A),
write(1/A),
(List = [] -> true; write(' + ')),
print_egyptian(List).
print_egyptian(X, Y):-
writef('Egyptian fraction for %t/%t: ', [X, Y]),
(X > Y ->
N is X//Y,
writef('[%t] ', [N]),
X1 is X mod Y
;
X1 = X
),
egyptian(X1, Y, E),
print_egyptian(E),
nl.
max_terms_and_denominator1(D, Max_terms, Max_denom, Max_terms1, Max_denom1):-
max_terms_and_denominator1(D, 1, Max_terms, Max_denom, Max_terms1, Max_denom1).
max_terms_and_denominator1(D, D, Max_terms, Max_denom, Max_terms, Max_denom):- !.
max_terms_and_denominator1(D, N, Max_terms, Max_denom, Max_terms1, Max_denom1):-
Max_terms1 = f(_, _, _, Len1),
Max_denom1 = f(_, _, _, Max1),
egyptian(N, D, E),
length(E, Len),
last(E, Max),
(Len > Len1 ->
Max_terms2 = f(N, D, E, Len)
;
Max_terms2 = Max_terms1
),
(Max > Max1 ->
Max_denom2 = f(N, D, E, Max)
;
Max_denom2 = Max_denom1
),
N1 is N + 1,
max_terms_and_denominator1(D, N1, Max_terms, Max_denom, Max_terms2, Max_denom2).
max_terms_and_denominator(N, Max_terms, Max_denom):-
max_terms_and_denominator(N, 1, Max_terms, Max_denom, f(0, 0, [], 0),
f(0, 0, [], 0)).
max_terms_and_denominator(N, N, Max_terms, Max_denom, Max_terms, Max_denom):-!.
max_terms_and_denominator(N, N1, Max_terms, Max_denom, Max_terms1, Max_denom1):-
max_terms_and_denominator1(N1, Max_terms2, Max_denom2, Max_terms1, Max_denom1),
N2 is N1 + 1,
max_terms_and_denominator(N, N2, Max_terms, Max_denom, Max_terms2, Max_denom2).
show_max_terms_and_denominator(N):-
writef('Proper fractions with most terms and largest denominator, limit = %t:\n', [N]),
max_terms_and_denominator(N, f(N_max_terms, D_max_terms, E_max_terms, Len),
f(N_max_denom, D_max_denom, E_max_denom, Max)),
writef('Most terms (%t): %t/%t = ', [Len, N_max_terms, D_max_terms]),
print_egyptian(E_max_terms),
nl,
count_digits(Max, Digits),
writef('Largest denominator (%t digits): %t/%t = ', [Digits, N_max_denom, D_max_denom]),
print_egyptian(E_max_denom),
nl.
main:-
print_egyptian(43, 48),
print_egyptian(5, 121),
print_egyptian(2014, 59),
nl,
show_max_terms_and_denominator(100),
nl,
show_max_terms_and_denominator(1000).</syntaxhighlight>
{{out}}
<pre>
Egyptian fraction for 43/48: 1/2 + 1/3 + 1/16
Egyptian fraction for 5/121: 1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1527612795...3418846225
Egyptian fraction for 2014/59: [34] 1/8 + 1/95 + 1/14947 + 1/670223480
Proper fractions with most terms and largest denominator, limit = 100:
Most terms (8): 44/53 = 1/2 + 1/4 + 1/13 + 1/307 + 1/120871 + 1/20453597227 + 1/6972493991...6783218655 + 1/1458470173...7836808420
Largest denominator (150 digits): 8/97 = 1/13 + 1/181 + 1/38041 + 1/1736503177 + 1/3769304102927363485 + 1/1894353789...8154430149 + 1/5382864419...4225813153 + 1/5795045870...3909789665
Proper fractions with most terms and largest denominator, limit = 1000:
Most terms (13): 641/796 = 1/2 + 1/4 + 1/19 + 1/379 + 1/159223 + 1/28520799973 + 1/9296411783...1338400861 + 1/1008271507...4174730681 + 1/1219933718...8484537833 + 1/1860297848...1025882029 + 1/4614277444...8874327093 + 1/3193733450...1456418881 + 1/2039986670...2410165441
Largest denominator (2847 digits): 36/457 = 1/13 + 1/541 + 1/321409 + 1/114781617793 + 1/1482167225...0844346913 + 1/2510651068...4290086881 + 1/7353930250...3326272641 + 1/6489634815...7391865217 + 1/5264420004...5476206145 + 1/3695215730...1238141889 + 1/2048192894...4706590593 + 1/8390188268...5525592705
</pre>
=={{header|Python}}==
===Procedural===
<
from math import ceil
Line 1,560 ⟶ 2,508:
dstr = str(denommax[0])
print('Denominator max is %r with %i digits %s...%s' %
(denommax[1], len(dstr), dstr[:5], dstr[-5:]))</
{{out}}
Line 1,574 ⟶ 2,522:
See the '''unfoldr''' function below:
{{Works with|Python|3.7}}
<
from fractions import Fraction
Line 1,596 ⟶ 2,544:
)) if n else Nothing()
fr = Fraction
return list(map(neg,
Line 1,713 ⟶ 2,661:
# MAIN ---
if __name__ == '__main__':
main()</
{{Out}}
<pre>Three values as Eqyptian fractions:
Line 1,734 ⟶ 2,682:
=={{header|Racket}}==
<
(define (real->egyptian-list R)
(define (inr r rv)
Line 1,782 ⟶ 2,730:
(module+ test (require tests/eli-tester)
(test (real->egyptian-list 43/48) => '(1/2 1/3 1/16)))</
{{out}}
Line 1,848 ⟶ 2,796:
89823812369...]
1 test passed</pre>
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku" line>role Egyptian {
method gist {
join ' + ',
("[{self.floor}]" if self.abs >= 1),
map {"1/$_"}, self.denominators;
}
method denominators {
my ($x, $y) = self.nude;
$x %= $y;
my @denom = gather ($x, $y) = -$y % $x, $y * take ($y / $x).ceiling
while $x;
}
}
say .nude.join('/'), " = ", $_ but Egyptian for 43/48, 5/121, 2014/59;
my @sample = map { $_ => .denominators },
grep * < 1,
map {$_ but Egyptian},
(2 .. 99 X/ 2 .. 99);
say .key.nude.join("/"),
" has max denominator, namely ",
.value.max
given max :by(*.value.max), @sample;
say .key.nude.join("/"),
" has max number of denominators, namely ",
.value.elems
given max :by(*.value.elems), @sample;</syntaxhighlight>
{{out}}
<pre>43/48 = 1/2 + 1/3 + 1/16
5/121 = 1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1527612795642093418846225
2014/59 = [34] + 1/8 + 1/95 + 1/14947 + 1/670223480
8/97 has max denominator, namely 579504587067542801713103191859918608251030291952195423583529357653899418686342360361798689053273749372615043661810228371898539583862011424993909789665
8/97 has max number of denominators, namely 8</pre>
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" line>role Egyptian {
method gist { join ' + ', map {"1/$_"}, self.list }
method list {
my $sum = 0;
gather for 2 .. * {
last if $sum == self;
$sum += 1 / .take unless $sum + 1 / $_ > self;
}
}
}
say 5/4 but Egyptian;</syntaxhighlight>
{{out}}
<pre>1/2 + 1/3 + 1/4 + 1/6</pre>
The list of terms grows exponentially with the value of the fraction, though.
=={{header|REXX}}==
<
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 1,902 ⟶ 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)</
'''output''' when the input used is: <tt> 43/48 </tt>
<pre>
Line 1,924 ⟶ 2,930:
Also, the same program is used for the 1-, 2-, and 3-digit extra credit task.
<
parse arg top . /*get optional parameter from the C.L. */
if top=='' then top=99 /*Not specified? Then use the default.*/
Line 1,947 ⟶ 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. */</
'''output''' for all 1- and 2-digit integers when using the default input:
<pre>
Line 1,959 ⟶ 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}}
<
ans = []
if fr >= 1
Line 1,994 ⟶ 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</
{{out}}
Line 2,005 ⟶ 3,083:
579504587067542801713103191859918608251030291952195423583529357653899418686342360361798689053273749372615043661810228371898539583862011424993909789665
</pre>
=={{header|Rust}}==
<syntaxhighlight lang="rust">
use num_bigint::BigInt;
use num_integer::Integer;
use num_traits::{One, Zero};
use std::fmt;
#[derive(Debug, Clone, PartialEq, PartialOrd)]
struct Rational {
nominator: BigInt,
denominator: BigInt,
}
impl Rational {
fn new(n: &BigInt, d: &BigInt) -> Rational {
assert!(!d.is_zero(), "denominator cannot be 0");
// simplify if possible
let c = n.gcd(d);
Rational {
nominator: n / &c,
denominator: d / &c,
}
}
fn is_proper(&self) -> bool {
self.nominator < self.denominator
}
fn to_egyptian(&self) -> Vec<Rational> {
let mut frac: Vec<Rational> = Vec::new();
let mut current: Rational;
if !self.is_proper() {
// input is grater than 1
// store the integer part
frac.push(Rational::new(
&self.nominator.div_floor(&self.denominator),
&One::one(),
));
// calculate the remainder
current = Rational::new(
&self.nominator.mod_floor(&self.denominator),
&self.denominator,
);
} else {
current = self.clone();
}
while !current.nominator.is_one() {
let div = current.denominator.div_ceil(¤t.nominator);
// store the term
frac.push(Rational::new(&One::one(), &div));
current = Rational::new(
&(-¤t.denominator).mod_floor(¤t.nominator),
match current.denominator.checked_mul(&div).as_ref() {
Some(r) => r,
_ => break,
},
);
}
frac.push(current);
frac
}
}
impl fmt::Display for Rational {
fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
if self.denominator.is_one() {
// for integers only display the integer part
write!(f, "{}", self.nominator)
} else {
write!(f, "{}/{}", self.nominator, self.denominator)
}
}
}
fn rational_vec_to_string(vec: Vec<Rational>) -> String {
let mut p = vec
.iter()
.fold(String::new(), |acc, num| (acc + &num.to_string() + ", "));
if p.len() > 1 {
p.truncate(p.len() - 2);
}
format!("[{}]", p)
}
fn run_max_searches(x: usize) {
// generate all proper fractions with 2 digits
let pairs = (1..x).flat_map(move |i| (i + 1..x).map(move |j| (i, j)));
let mut max_length = (0, Rational::new(&BigInt::from(1), &BigInt::from(1)));
let mut max_denom = (
Zero::zero(),
Rational::new(&BigInt::from(1), &BigInt::from(1)),
);
for (i, j) in pairs {
let e = Rational::new(&BigInt::from(i), &BigInt::from(j)).to_egyptian();
if e.len() > max_length.0 {
max_length = (e.len(), Rational::new(&BigInt::from(i), &BigInt::from(j)));
}
if e.last().unwrap().denominator > max_denom.0 {
max_denom = (
e.last().unwrap().denominator.clone(),
Rational::new(&BigInt::from(i), &BigInt::from(j)),
);
}
}
println!(
"Maximum length of terms is for {} with {} terms",
max_length.1, max_length.0
);
println!("{}", rational_vec_to_string(max_length.1.to_egyptian()));
println!(
"Maximum denominator is for {} with {} terms",
max_denom.1, max_denom.0
);
println!("{}", rational_vec_to_string(max_denom.1.to_egyptian()));
}
fn main() {
let tests = [
Rational::new(&BigInt::from(43), &BigInt::from(48)),
Rational::new(&BigInt::from(5), &BigInt::from(121)),
Rational::new(&BigInt::from(2014), &BigInt::from(59)),
];
for test in tests.iter() {
println!("{} -> {}", test, rational_vec_to_string(test.to_egyptian()));
}
run_max_searches(100);
run_max_searches(1000);
}
</syntaxhighlight>
{{out}}
<pre>
43/48 -> [1/2, 1/3, 1/16]
5/121 -> [1/25, 1/757, 1/763309, 1/873960180913, 1/1527612795642093418846225]
2014/59 -> [34, 1/8, 1/95, 1/14947, 1/670223480]
Maximum length of terms is for 8/97 with 8 terms
[1/13, 1/181, 1/38041, 1/1736503177, 1/3769304102927363485, 1/18943537893793408504192074528154430149, 1/538286441900380211365817285104907086347439746130226973253778132494225813153, 1/579504587067542801713103191859918608251030291952195423583529357653899418686342360361798689053273749372615043661810228371898539583862011424993909789665]
Maximum denominator is for 8/97 with 5795045870675428017131...3909789665 terms (150 digits)
[1/13, 1/181, 1/38041, 1/1736503177, 1/3769304102927363485, 1/18943537893793408504192074528154430149, 1/538286441900380211365817285104907086347439746130226973253778132494225813153, 1/5795045870675428017131...3909789665]
Maximum length of terms is for 529/914 with 13 terms:
[1/2, 1/13, 1/541, 1/321409, 1/114781617793, 1/14821672255960844346913, 1/251065106814993628596500876449600804290086881, 1/73539302503361520198362339236500915390885795679264404865887253300925727812630083326272641, 1/6489634815217096741...91865217, 1/52644200043...5476206145, 1/36952157309...38141889, 1/204819289476534...06590593, 1/83901882683...25592705]
Maximum denominator is for 36/457 with 83901882683...25592705 (2847 digits)
</pre>
=={{header|Scala}}==
{{trans|Java}}
<syntaxhighlight lang="scala">import scala.annotation.tailrec
import scala.collection.mutable
import scala.collection.mutable.{ArrayBuffer, ListBuffer}
abstract class Frac extends Comparable[Frac] {
val num: BigInt
val denom: BigInt
def toEgyptian: List[Frac] = {
if (num == 0) {
return List(this)
}
val fracs = new ArrayBuffer[Frac]
if (num.abs >= denom.abs) {
val div = Frac(num / denom, 1)
val rem = this - div
fracs += div
egyptian(rem.num, rem.denom, fracs)
} else {
egyptian(num, denom, fracs)
}
fracs.toList
}
@tailrec
private def egyptian(n: BigInt, d: BigInt, fracs: mutable.Buffer[Frac]): Unit = {
if (n == 0) {
return
}
val n2 = BigDecimal.apply(n)
val d2 = BigDecimal.apply(d)
val (divbd, rembd) = d2./%(n2)
var div = divbd.toBigInt()
if (rembd > 0) {
div = div + 1
}
fracs += Frac(1, div)
var n3 = -d % n
if (n3 < 0) {
n3 = n3 + n
}
val d3 = d * div
val f = Frac(n3, d3)
if (f.num == 1) {
fracs += f
return
}
egyptian(f.num, f.denom, fracs)
}
def unary_-(): Frac = {
Frac(-num, denom)
}
def +(rhs: Frac): Frac = {
Frac(
num * rhs.denom + rhs.num * denom,
denom * rhs.denom
)
}
def -(rhs: Frac): Frac = {
Frac(
num * rhs.denom - rhs.num * denom,
denom * rhs.denom
)
}
override def compareTo(rhs: Frac): Int = {
val ln = num * rhs.denom
val rn = rhs.num * denom
ln.compare(rn)
}
def canEqual(other: Any): Boolean = other.isInstanceOf[Frac]
override def equals(other: Any): Boolean = other match {
case that: Frac =>
(that canEqual this) &&
num == that.num &&
denom == that.denom
case _ => false
}
override def hashCode(): Int = {
val state = Seq(num, denom)
state.map(_.hashCode()).foldLeft(0)((a, b) => 31 * a + b)
}
override def toString: String = {
if (denom == 1) {
return s"$num"
}
s"$num/$denom"
}
}
object Frac {
def apply(n: BigInt, d: BigInt): Frac = {
if (d == 0) {
throw new IllegalArgumentException("Parameter d may not be zero.")
}
var nn = n
var dd = d
if (nn == 0) {
dd = 1
} else if (dd < 0) {
nn = -nn
dd = -dd
}
val g = nn.gcd(dd)
if (g > 0) {
nn /= g
dd /= g
}
new Frac {
val num: BigInt = nn
val denom: BigInt = dd
}
}
}
object EgyptianFractions {
def main(args: Array[String]): Unit = {
val fracs = List.apply(
Frac(43, 48),
Frac(5, 121),
Frac(2014, 59)
)
for (frac <- fracs) {
val list = frac.toEgyptian
val it = list.iterator
print(s"$frac -> ")
if (it.hasNext) {
val value = it.next()
if (value.denom == 1) {
print(s"[$value]")
} else {
print(value)
}
}
while (it.hasNext) {
val value = it.next()
print(s" + $value")
}
println()
}
for (r <- List(98, 998)) {
println()
if (r == 98) {
println("For proper fractions with 1 or 2 digits:")
} else {
println("For proper fractions with 1, 2 or 3 digits:")
}
var maxSize = 0
var maxSizeFracs = new ListBuffer[Frac]
var maxDen = BigInt(0)
var maxDenFracs = new ListBuffer[Frac]
val sieve = Array.ofDim[Boolean](r + 1, r + 2)
for (i <- 0 until r + 1) {
for (j <- i + 1 until r + 1) {
if (!sieve(i)(j)) {
val f = Frac(i, j)
val list = f.toEgyptian
val listSize = list.size
if (listSize > maxSize) {
maxSize = listSize
maxSizeFracs.clear()
maxSizeFracs += f
} else if (listSize == maxSize) {
maxSizeFracs += f
}
val listDen = list.last.denom
if (listDen > maxDen) {
maxDen = listDen
maxDenFracs.clear()
maxDenFracs += f
} else if (listDen == maxDen) {
maxDenFracs += f
}
if (i < r / 2) {
var k = 2
while (j * k <= r + 1) {
sieve(i * k)(j * k) = true
k = k + 1
}
}
}
}
}
println(s" largest number of items = $maxSize")
println(s"fraction(s) with this number : ${maxSizeFracs.toList}")
val md = maxDen.toString()
print(s" largest denominator = ${md.length} digits, ")
println(s"${md.substring(0, 20)}...${md.substring(md.length - 20)}")
println(s"fraction(s) with this denominator : ${maxDenFracs.toList}")
}
}
}</syntaxhighlight>
{{out}}
<pre>43/48 -> 1/2 + 1/3 + 1/16
5/121 -> 1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1527612795642093418846225
2014/59 -> [34] + 1/8 + 1/95 + 1/14947 + 1/670223480
For proper fractions with 1 or 2 digits:
largest number of items = 8
fraction(s) with this number : List(8/97, 44/53)
largest denominator = 150 digits, 57950458706754280171...62011424993909789665
fraction(s) with this denominator : List(8/97)
For proper fractions with 1, 2 or 3 digits:
largest number of items = 13
fraction(s) with this number : List(529/914, 641/796)
largest denominator = 2847 digits, 83901882683345018663...38431266995525592705
fraction(s) with this denominator : List(36/457, 529/914)</pre>
=={{header|Sidef}}==
{{trans|Ruby}}
<
var ans = []
if (fr >= 1) {
Line 2,043 ⟶ 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]</
{{out}}
<pre>
Line 2,055 ⟶ 3,515:
=={{header|Tcl}}==
<
proc egyptian {num denom} {
set result {}
Line 2,066 ⟶ 3,526:
}
return $result
}</
Demonstrating:
{{works with|Tcl|8.6}}
<
proc efrac {fraction} {
Line 2,103 ⟶ 3,563:
}
puts "$maxtf has maximum number of terms = [efrac $maxtf]"
puts "$maxdf has maximum denominator = [efrac $maxdf]"</
{{out}}
<pre>
Line 2,117 ⟶ 3,577:
=={{header|Visual Basic .NET}}==
{{trans|D}}
<
Imports System.Text
Line 2,297 ⟶ 3,757:
End Sub
End Module</
{{out}}
<pre>43/48 => [1/2, 1/3, 1/16]
Line 2,304 ⟶ 3,764:
Term max is 97/53 with 9 terms
Denominator max is 8/97 with 150 digits 57950...89665</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-big}}
We use the BigRat class in the above module to represent arbitrary size fractions.
<syntaxhighlight lang="wren">import "./big" for BigInt, BigRat
var toEgyptianHelper // recursive
toEgyptianHelper = Fn.new { |n, d, fracs|
if (n == BigInt.zero) return
var divRem = d.divMod(n)
var div = divRem[0]
if (divRem[1] > BigInt.zero) div = div.inc
fracs.add(BigRat.new(BigInt.one, div))
var n2 = (-d) % n
if (n2 < BigInt.zero) n2 = n2 + n
var d2 = d * div
var f = BigRat.new(n2, d2)
if (f.num == BigInt.one) {
fracs.add(f)
return
}
toEgyptianHelper.call(f.num, f.den, fracs)
}
var toEgyptian = Fn.new { |r|
if (r.num == BigInt.zero) return [r]
var fracs = []
if (r.num.abs >= r.den.abs) {
var div = BigRat.new(r.num/r.den, BigInt.one)
var rem = r - div
fracs.add(div)
toEgyptianHelper.call(rem.num, rem.den, fracs)
} else {
toEgyptianHelper.call(r.num, r.den, fracs)
}
return fracs
}
BigRat.showAsInt = true
var fracs = [BigRat.new(43, 48), BigRat.new(5, 121), BigRat.new(2014, 59)]
for (frac in fracs) {
var list = toEgyptian.call(frac)
System.print("%(frac) -> %(list.join(" + "))")
}
for (r in [98, 998]) {
if (r == 98) {
System.print("\nFor proper fractions with 1 or 2 digits:")
} else {
System.print("\nFor proper fractions with 1, 2 or 3 digits:")
}
var maxSize = 0
var maxSizeFracs = []
var maxDen = BigInt.zero
var maxDenFracs = []
var sieve = List.filled(r + 1, null) // to eliminate duplicates
for (i in 0..r) sieve[i] = List.filled(r + 2, false)
for (i in 1..r) {
for (j in (i + 1)..(r + 1)) {
if (!sieve[i][j]) {
var f = BigRat.new(i, j)
var list = toEgyptian.call(f)
var listSize = list.count
if (listSize > maxSize) {
maxSize = listSize
maxSizeFracs.clear()
maxSizeFracs.add(f)
} else if (listSize == maxSize) {
maxSizeFracs.add(f)
}
var listDen = list[-1].den
if (listDen > maxDen) {
maxDen = listDen
maxDenFracs.clear()
maxDenFracs.add(f)
} else if (listDen == maxDen) {
maxDenFracs.add(f)
}
if (i < r / 2) {
var k = 2
while (true) {
if (j * k > r + 1) break
sieve[i * k][j * k] = true
k = k + 1
}
}
}
}
}
System.print(" largest number of items = %(maxSize)")
System.print(" fraction(s) with this number : %(maxSizeFracs)")
var md = maxDen.toString
System.write(" largest denominator = %(md.count) digits, ")
System.print("%(md[0...20])...%(md[-20..-1])")
System.print(" fraction(s) with this denominator : %(maxDenFracs)")
}</syntaxhighlight>
{{out}}
<pre>
43/48 -> 1/2 + 1/3 + 1/16
5/121 -> 1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1527612795642093418846225
2014/59 -> 34 + 1/8 + 1/95 + 1/14947 + 1/670223480
For proper fractions with 1 or 2 digits:
largest number of items = 8
fraction(s) with this number : [8/97, 44/53]
largest denominator = 150 digits, 57950458706754280171...62011424993909789665
fraction(s) with this denominator : [8/97]
For proper fractions with 1, 2 or 3 digits:
largest number of items = 13
fraction(s) with this number : [529/914, 641/796]
largest denominator = 2847 digits, 83901882683345018663...38431266995525592705
fraction(s) with this denominator : [36/457, 529/914]
</pre>
=={{header|zkl}}==
{{trans|Tcl}}
<
fcn egyptian(num,denom){
result,t := List(),Void;
Line 2,327 ⟶ 3,903:
else String("1/",denom);
}).concat(" + ")
}</
<
println("%s/%s --> %s".fmt(n,d, egyptian(n,d):efrac(_)));
}</
{{out}}
<pre>
Line 2,338 ⟶ 3,914:
</pre>
For the big denominators, use GMP (Gnu Multi Precision).
<
lenMax,denomMax := List(0,Void),List(0,Void);
foreach n,d in (Walker.cproduct([1..99],[1..99])){ // 9801 fractions
Line 2,349 ⟶ 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,*]));</
{{out}}
<pre>
| |||