CloudFlare suffered a massive security issue affecting all of its customers, including Rosetta Code. All passwords not changed since February 19th 2017 have been expired, and session cookie longevity will be reduced until late March.--Michael Mol (talk) 05:15, 25 February 2017 (UTC)

Egyptian fractions

From Rosetta Code
Egyptian fractions is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

An Egyptian fraction is the sum of distinct unit fractions such as:

.

Each fraction in the expression has a numerator equal to and a denominator that is a positive integer, and all the denominators are distinct (i.e., no repetitions).

Fibonacci's Greedy algorithm for Egyptian fractions expands the fraction to be represented by repeatedly performing the replacement

(simplifying the 2nd term in this replacement as necessary, and where is the ceiling function).

Proper and improper fractions must be able to be expressed.

Proper fractions   are of the form where and are positive integers, such that , and
improper fractions are of the form where and are positive integers, such that ab.

(See the REXX programming example to view one method of expressing the whole number part of an improper fraction.)

For improper fractions, the integer part of any improper fraction should be first isolated and shown preceding the Egyptian unit fractions, and be surrounded by square brackets [n].

Task requirements
  • show the Egyptian fractions for: and and
  • for all proper fractions, where and are positive one-or two-digit (decimal) integers, find and show an Egyptian fraction that has:
  • the largest number of terms,
  • the largest denominator.
  • for all one-, two-, and three-digit integers (extra credit), find and show (as above).
Also see



D[edit]

Assuming the Python entry is correct, this code is equivalent. This requires the D module of the Arithmetic/Rational task.

Translation of: Python
import std.stdio, std.bigint, std.algorithm, std.range, std.conv, std.typecons,
arithmetic_rational: Rat = Rational;
 
Rat[] egyptian(Rat r) pure nothrow {
typeof(return) result;
 
if (r >= 1) {
if (r.denominator == 1)
return [r, Rat(0, 1)];
result = [Rat(r.numerator / r.denominator, 1)];
r -= result[0];
}
 
static enum mod = (in BigInt m, in BigInt n) pure nothrow =>
((m % n) + n) % n;
 
while (r.numerator != 1) {
immutable q = (r.denominator + r.numerator - 1) / r.numerator;
result ~= Rat(1, q);
r = Rat(mod(-r.denominator, r.numerator), r.denominator * q);
}
 
result ~= r;
return result;
}
 
void main() {
foreach (immutable r; [Rat(43, 48), Rat(5, 121), Rat(2014, 59)])
writefln("%s => %(%s %)", r, r.egyptian);
 
Tuple!(size_t, Rat) lenMax;
Tuple!(BigInt, Rat) denomMax;
 
foreach (immutable r; iota(1, 100).cartesianProduct(iota(1, 100))
.map!(nd => nd[].Rat).array.sort().uniq) {
immutable e = r.egyptian;
immutable eLen = e.length;
immutable eDenom = e.back.denominator;
if (eLen > lenMax[0])
lenMax = tuple(eLen, r);
if (eDenom > denomMax[0])
denomMax = tuple(eDenom, r);
}
writefln("Term max is %s with %d terms", lenMax[1], lenMax[0]);
immutable dStr = denomMax[0].text;
writefln("Denominator max is %s with %d digits %s...%s",
denomMax[1], dStr.length, dStr[0 .. 5], dStr[$ - 5 .. $]);
}
Output:
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

FreeBASIC[edit]

Library: GMP
' version 16-01-2017
' compile with: fbc -s console
 
#Define max 30
 
#Include Once "gmp.bi"
 
Dim Shared As Mpz_ptr num(max), den(max)
 
Function Egyptian_fraction(fraction As String, ByRef whole As Integer, range As Integer = 0) As Integer
 
If InStr(fraction,"/") = 0 Then
Print "Not a fraction, program will end"
Sleep 5000, 1
End
End If
 
Dim As Integer i, count
 
Dim As Mpz_ptr tmp_num, tmp_den, x, y, q
tmp_num = Allocate(Len(__Mpz_struct)) : Mpz_init(tmp_num)
tmp_den = Allocate(Len(__Mpz_struct)) : Mpz_init(tmp_den)
x = Allocate(Len(__Mpz_struct)) : Mpz_init(x)
y = Allocate(Len(__Mpz_struct)) : Mpz_init(y)
q = Allocate(Len(__Mpz_struct)) : Mpz_init(q)
 
For i = 1 To max ' clear the list
Mpz_set_ui(num(i), 0)
Mpz_set_ui(den(i), 0)
Next
 
i = InStr(fraction,"/")
Mpz_set_str(x, Left(fraction, i -1), 10)
Mpz_set_str(y, Right(fraction, Len(fraction) - i), 10)
 
' if it's a improper fraction make it proper fraction
If Mpz_cmp(x , y) > 0 Then
Mpz_fdiv_q(q, x, y)
whole = Mpz_get_ui(q)
Mpz_fdiv_r(x, x, q)
Else
whole = 0
End If
 
Mpz_gcd(q, x, y) ' check if reduction is possible
If Mpz_cmp_ui(q, 1) > 0 Then
If range <> 0 Then ' return if we do a range test
Return -1
Else
Mpz_fdiv_q(x, x, q)
Mpz_fdiv_q(y, y, q)
End If
End If
 
Mpz_set(num(count), x)
Mpz_set(den(count), y)
' Fibonacci's Greedy algorithm for Egyptian fractions
Do
If Mpz_cmp_ui(num(count), 1) = 0 Then Exit Do
Mpz_set(x, num(count))
Mpz_set(y, den(count))
Mpz_cdiv_q(q, y, x)
Mpz_set_ui(num(count), 1)
Mpz_set(den(count), q)
Mpz_mul(tmp_den, y, q)
Mpz_neg(y, y)
Mpz_mod(tmp_num, y, x)
count += 1
Mpz_gcd(q, tmp_num, tmp_den) ' check if reduction is possible
If Mpz_cmp_ui(q, 1) > 0 Then
Mpz_fdiv_q(tmp_num, tmp_num, q)
Mpz_fdiv_q(tmp_den, tmp_den, q)
End If
Mpz_set(num(count), tmp_num)
Mpz_set(den(count), tmp_den)
Loop
 
Mpz_clear(tmp_num) : Mpz_clear(tmp_den)
Mpz_clear(x) : Mpz_clear(y) :Mpz_clear(q)
 
Return count
 
End Function
 
Sub prt_solution(fraction As String, whole As Integer, count As Integer)
 
Print fraction; " = ";
 
If whole <> 0 Then
Print "["; Str(whole); "] + ";
End If
 
For i As Integer = 0 To count
Gmp_printf("%Zd/%Zd ", num(i), den(i))
If i <> count Then Print "+ ";
Next
Print
 
End Sub
 
' ------=< MAIN >=------
 
Dim As Integer n, d, number, improper, max_term, max_size
Dim As String str_in, max_term_str, max_size_str, m_str
Dim As ZString Ptr gmp_str : gmp_str = Allocate(1000000)
 
For n = 0 To max
num(n) = Allocate(Len(__Mpz_struct)) : Mpz_init(num(n))
den(n) = Allocate(Len(__Mpz_struct)) : Mpz_init(den(n))
Next
 
Data "43/48", "5/121", "2014/59"
' 4/121 = 12/363 = 11/263 + 1/363 = 1/33 + 1/363
' 5/121 = 4/121 + 1/121 = 1/33 + 1/121 + 1/363
' 2014/59 = 34 + 8/59
' 8/59 = 1/8 + 5/472 = 1/8 + 4/472 + 1/472 = 1/8 + 1/118 + 1/472
 
For n = 1 To 3
Read str_in
number = Egyptian_fraction(str_in, improper)
prt_solution(str_in, improper, number)
Print
Next
 
Dim As Integer a = 1 , b = 99
 
Do
For d = a To b
For n = 1 To d -1
str_in = Str(n) + "/" + Str(d)
number = Egyptian_fraction(str_in, improper,1)
If number = -1 Then Continue For ' skip
If number > max_term Then
max_term = number
max_term_str = str_in
ElseIf number = max_term Then
max_term_str += ", " & str_in
End If
Mpz_get_str(gmp_str, 10, den(number))
If Len(*gmp_str) > max_size Then
max_size = Len(*gmp_str)
max_size_str = str_in
m_str = *gmp_str
ElseIf max_size = Len(*gmp_str) Then
max_size_str += ", " & str_in
End If
Next
Next
Print
Print "for 1 to"; Len(Str(b)); " digits"
Print "Largest number of terms is"; max_term +1; " for "; max_term_str
Print "Largest size for denominator is"; max_size; " for "; max_size_str
 
If b = 999 Then Exit Do
a = b +1 : b = b * 10 +9
Loop
 
For n = 0 To max
Mpz_clear(num(n))
Mpz_clear(den(n))
Next
 
DeAllocate(gmp_str)
 
' empty keyboard buffer
While InKey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End
Output:
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 1 to 2 digits
Largest number of terms is 8 for 44/53, 8/97
Largest size for denominator is 150 for 8/97

for 1 to 3 digits
Largest number of terms is 13 for 641/796, 529/914
Largest size for denominator is 2847 for 36/457, 529/914

Haskell[edit]

import Data.Ratio
 
egiptianFraction :: Integral a => Ratio a -> [Ratio a]
egiptianFraction n
| n < 0 = map negate (egiptianFraction (-n))
| n == 0 = []
| x == 1 = [n]
| x > y = (x `div` y % 1) : egiptianFraction (x `mod` y % y)
| otherwise = (1 % r) : egiptianFraction ((-y) `mod` x % (y*r))
where x = numerator n
y = denominator n
r = y `div` x + 1

Testing:

λ> :m Test.QuickCheck
λ> quickCheck (\n -> n == (sum $ egiptianFraction n))
+++ OK, passed 100 tests.

Tasks:

import Data.List
import Data.Ord
 
task1 = mapM_ run [ 43 % 48, 5 % 121, 2014 % 59 ]
where run x = putStrLn $ show x ++ " = " ++ result x
result x = intercalate " + " $ show <$> egiptianFraction x
 
task21 n = maximumBy (comparing snd)
[ (a % b, length $ egiptianFraction (a % b))
| a <- [1..n], b <- [1..n], a < b ]
 
task22 n = maximumBy (comparing snd)
[ (a % b, maximum $ map denominator $ egiptianFraction (a % b))
| a <- [1..n], b <- [1..n], a < b]
 
λ> task1
43 % 48 = 1 % 2 + 1 % 3 + 1 % 16
5 % 121 = 1 % 25 + 1 % 757 + 1 % 763309 + 1 % 873960180913 + 1 % 1527612795642093418846225
2014 % 59 = 34 % 1 + 1 % 8 + 1 % 95 + 1 % 14947 + 1 % 670223480
λ> task21 99
(44 % 53, 8)
λ> task22 99
(8 % 97, 579504587067542801713103191859918608251030291952195423583529357653899418686342360361798689053273749372615043661810228371898539583862011424993909789665)
λ> task21 999
(641 % 796,13)
λ> task22 999
(529 % 914, 839018826833450186636781520007011999269820404906753180244759299287837378895397605613261469995626498719289835112392530430840514102146998625666594756995273418015600023494049208108894185781774002683063204252356172520941088783702738286944210460710059319691268110283467445381026653628599765684739105388642310044785844902157076919003735231543781785073393176144167688252446541416466418608465458502997971425428342769433127784560570193376772878336217849260872114137931351960543608384244009505664253173875705234889570853924105640193619301332776989688248555027054395237907581951261868280899150574360164800187964167274323078311078867593844043149124596271281252530924719121766925749760855109100066731841478262812686642693395896229983745226277793055820609058348269152190083695704685769622011655159174272326647342695589818127126303038171968768650476413027459205291075571637957597356820188031655122749743652301268394542123970892422944335857917641636041892192547135178153602038877677614358281581103685526041329841496863410305888255234495015115912388514981113593387572720476744188169200130515719608747338810136728267784013352396910979904545913458536243327311977805126410065576961237640824852114328884086581542091492600312838425666927627674227053793897767395465326589843035773944346372949759909905561209334216847158156644884281300512699910530092870919061876615770708519243818676366245477462042294267674677954783726990349386117468071932874021023714524610740225814235147693954027910741673103980749749728106483987721602738673173009362802337092908847797499475895347112889339502928407808058670297722175686638678788738689803945574002805677250463286479363670076942509109589495377221095405979217163821481666646160815221224686562530536116613645305335922819524037829878961518170177968768364853399057357772141655622381280196908637031556436461404285930426436983658106288733881761514992109680298995922754466040011586713812553117621857109517258943846004179432521131844156242428351270188803919554398620084668514054504414062276012292497375238210886595006249453460414790147611422121782194848803348777061816460876697945418158442269512987729152441940326466631610424906158237288218706447963113019239557885486647314085357651895226117364760315394354624547919209138539180807829672545924239541758108877100331729470119526373928796447673951888289511964811633025369821156695934557103429921063387965046715070102916811976552584464153981214277622597308113449320462341683055200576571910241686615924531368198770946893858410058348221985603151428153382461711196734214085852523778422630907646235900752317571022131569421231196329080023952364788544301495422061066036911772385739659997665503832444529713544286955548310166168837889046149061296461059432238621602179724809510024772127497080258401694929973105184832214622785679651550368465524821062859837409907538269572622296774545103747438431266995525592705)
 


J[edit]

Solution:
   ef   =: [: (}.~ 0={.) [: (, r2ef)/ 0 1 #: x: 
r2ef =: (<(<0);0) { ((] , -) >:@:<.&.%)^:((~:<.)@:%)@:{:^:a:
Examples (required):
   (; ef)&> 43r48 5r121 2014r59
+-------+--------------------------------------------------------------+
|43r48 |1r2 1r3 1r16 |
+-------+--------------------------------------------------------------+
|5r121 |1r25 1r757 1r763309 1r873960180913 1r1527612795642093418846225|
+-------+--------------------------------------------------------------+
|2014r59|34 1r8 1r95 1r14947 1r670223480 |
+-------+--------------------------------------------------------------+
Examples (extended):
   NB. ef for all 1- and 2-digit fractions
EF2 =: ef :: _1:&.> (</~ * %/~) i. 10^2x
 
 
NB. longest ef for 1- or 2-digit fraction
($ #: (i. >./)@:,)#&>EF2
8 97
# ef 8r97
8
 
NB. largest denom among for 1- and 2-digit fractions
($ #: (i. <./)@:|@:(<./&>)@:,) EF2
8 97
_80 ]\ ": % <./ ef 8r97
57950458706754280171310319185991860825103029195219542358352935765389941868634236
0361798689053273749372615043661810228371898539583862011424993909789665
 
NB. ef for all 1-,2-, and 3-digit fractions
EF3 =: ef :: _1:&.> (</~ * %/~) i. 10^3x
 
NB. longest ef for 1-, 2-,or 3-digit fraction
($ #: (i. >./)@:,)#&>EF3
529 914
# ef 529r914
13
 
NB. largest denom among for 1-, 2-, and 3-digit fractions
($ #: (i. <./)@:|@:(<./&>)@:,) EF3
36 457
_80 ]\ ": % <./ ef 36r457
83901882683345018663678152000701199926982040490675318024475929928783737889539760
56132614699956264987192898351123925304308405141021469986256665947569952734180156
00023494049208108894185781774002683063204252356172520941088783702738286944210460
71005931969126811028346744538102665362859976568473910538864231004478584490215707
69190037352315437817850733931761441676882524465414164664186084654585029979714254
28342769433127784560570193376772878336217849260872114137931351960543608384244009
50566425317387570523488957085392410564019361930133277698968824855502705439523790
75819512618682808991505743601648001879641672743230783110788675938440431491245962
71281252530924719121766925749760855109100066731841478262812686642693395896229983
74522627779305582060905834826915219008369570468576962201165515917427232664734269
55898181271263030381719687686504764130274592052910755716379575973568201880316551
22749743652301268394542123970892422944335857917641636041892192547135178153602038
87767761435828158110368552604132984149686341030588825523449501511591238851498111
35933875727204767441881692001305157196087473388101367282677840133523969109799045
45913458536243327311977805126410065576961237640824852114328884086581542091492600
31283842566692762767422705379389776739546532658984303577394434637294975990990556
12093342168471581566448842813005126999105300928709190618766157707085192438186763
66245477462042294267674677954783726990349386117468071932874021023714524610740225
81423514769395402791074167310398074974972810648398772160273867317300936280233709
29088477974994758953471128893395029284078080586702977221756866386787887386898039
45574002805677250463286479363670076942509109589495377221095405979217163821481666
64616081522122468656253053611661364530533592281952403782987896151817017796876836
48533990573577721416556223812801969086370315564364614042859304264369836581062887
33881761514992109680298995922754466040011586713812553117621857109517258943846004
17943252113184415624242835127018880391955439862008466851405450441406227601229249
73752382108865950062494534604147901476114221217821948488033487770618164608766979
45418158442269512987729152441940326466631610424906158237288218706447963113019239
55788548664731408535765189522611736476031539435462454791920913853918080782967254
59242395417581088771003317294701195263739287964476739518882895119648116330253698
21156695934557103429921063387965046715070102916811976552584464153981214277622597
30811344932046234168305520057657191024168661592453136819877094689385841005834822
19856031514281533824617111967342140858525237784226309076462359007523175710221315
69421231196329080023952364788544301495422061066036911772385739659997665503832444
52971354428695554831016616883788904614906129646105943223862160217972480951002477
21274970802584016949299731051848322146227856796515503684655248210628598374099075
38269572622296774545103747438431266995525592705

Mathematica[edit]

frac[n_] /; IntegerQ[1/n] := frac[n] = {n};
frac[n_] :=
frac[n] =
With[{p = Numerator[n], q = Denominator[n]},
Prepend[frac[Mod[-q, p]/(q Ceiling[1/n])], 1/Ceiling[1/n]]];
disp[f_] :=
StringRiffle[
SequenceCases[f,
l : {_, 1 ...} :>
If[Length[l] == 1 && l[[1]] < 1, ToString[l[[1]], InputForm],
"[" <> ToString[Length[l]] <> "]"]], " + "] <> " = " <>
ToString[Numerator[Total[f]]] <> "/" <>
ToString[Denominator[Total[f]]];
Print[disp[frac[43/48]]];
Print[disp[frac[5/121]]];
Print[disp[frac[2014/59]]];
fracs = Flatten[Table[frac[p/q], {q, 99}, {p, q}], 1];
Print[disp[MaximalBy[fracs, Length@*Union][[1]]]];
Print[disp[MaximalBy[fracs, Denominator@*Last][[1]]]];
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]]]];
Output:
1/2 + 1/3 + 1/16 = 43/48
1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1527612795642093418846225 = 5/121
[34] + 1/8 + 1/95 + 1/14947 + 1/670223480 = 2014/59
1/2 + 1/4 + 1/13 + 1/307 + 1/120871 + 1/20453597227 + 1/697249399186783218655 + 1/1458470173998990524806872692984177836808420 = 44/53
1/13 + 1/181 + 1/38041 + 1/1736503177 + 1/3769304102927363485 + 1/18943537893793408504192074528154430149 + 1/538286441900380211365817285104907086347439746130226973253778132494225813153 + 1/579504587067542801713103191859918608251030291952195423583529357653899418686342360361798689053273749372615043661810228371898539583862011424993909789665 = 8/97
1/2 + 1/4 + 1/19 + 1/379 + 1/159223 + 1/28520799973 + 1/929641178371338400861 + 1/1008271507277592391123742528036634174730681 + 1/1219933718865393655364635368068124756713122928811333803786753398211072842948484537833 + 1/1860297848030936654742608399135821395565274404917258533393305147319524009551744684579405649080712180254407780735949179513154143641842892458088536544987153757401025882029 + 1/4614277444518045184646591832326467411359277711335974416082881814986405515888533562332069783067894981850924485553345190160771506460024406127868096951360637582674289834858262576425271895218431296391169922044160278696744025988461165811212428548328350795432691637759392474030879286312785400132190057899968737693594392669884878193448874327093 + 1/31937334502481972335865307630139228000187060941658399518862518849553429993133277230560087986574331290756232125775998863890963263813589266879406694561350952988662850757053371133819179770003609046815203982179108798005308113258134895569927488690118483730232440575942894680942308888321353318333183158977270294582315388855860989819894602178852719674244639951777398683083694723999674418435726557523519535770015019287382321071804865681731226989916286199314883016472947639367666251368202759691810399195092598892275413777035275182318485652713871000041272524440519262054008953943029365257325370839037761555465335452562216651250516983405134378252470216494582635109781712938341456418881 + 1/2039986670246850822853427080268636607703538330430958135006350872460188775376402385474575383380701179275926633909293920375037781006938834602683282504456671345800481611955974906577358109966753513899436209725756764159504134559394933538420714469300931804842468643272796657406808805007786178371184391663721349034183315512035012402176731111044506314978549915206516847224339930494935465558632905912262959736737614637514921726288403470224139024425700070180324623265095949577758695292697562554242228453440276043742370033993859881981612938703208463591285870376619588297958810138295747858827756577616148419423031480258559516303907719233914603343421735341220080271152090557188286289527661792734931298102513902518914250419121432886312102736349552224188669212688846219382874287241971706387850290821170997846726526589069990513808709560793139660289273086403155344460608865436195352720549406793512677065107181955781264579349071905411393100989250722104770801720673437692418988638492506057962758754921169589084980707251205329924087857682559921447010465898318288868258062129919867004394488124710647843586978379399594154917914477913086776811741840849911967039211773201428676384229432761943488196359561416605048969002045397348240530911560634680322446588472763785839765588633770016209055874572792498932175778494089116461654628549726895871636209026849103988563732410165441 = 641/796
1/13 + 1/541 + 1/321409 + 1/114781617793 + 1/14821672255960844346913 + 1/251065106814993628596500876449600804290086881 + 1/73539302503361520198362339236500915390885795679264404865887253300925727812630083326272641 + 1/6489634815217096741758907148982381236931234341288936993640630568353888026513046373352130623124225014404918014072680355409470797372507720812828610332359154836067922616607391865217 + 1/52644200043597301715163084170074049765863371513744701000308778672552161021188727897845435784419167578097570308323221316037189809321236639774156001218848770417914304730719451756764847141999454715415348579218576135692260706546084789833559164567239198064491721524233401718052341737694961761810858726456915514545036448002629051435498625211733293978125476206145 + 1/3695215730973720191743335450900515442837964059737103132125137784392340041085824276783333540815086968586494259680343732030671448522298751008735945486795776365973142745077411841504712940444458881229478108614230774637316342940593842925604630011475333378620376362943942755446627099104200059416153812858633723638212819657597061963458758259287734950993940819872945202809437805131650984566124057319228963533088559443909352453788455968978250113376533423265233637558939144535732287317303130488802163512444658441011602922480039143050047663394967808639154754442570791381496210122415541628843804495020590646687354364355396925939868087995781911240513904752765014910531863571167632659092232428610030201325032663259931238141889 + 1/20481928947653467858867964360215698922460866349989714221296388791180533521147068328398292448571350580917144516243144419767021450972552458770890215041236338405232471846144964422722088363577942656244304369314740680337368003341749927848292268159627280776486153786277410225081205358330757686606252814923029488556248114378465151886875778980493919811102286892641254175976181063891774788890129279669791215911728886439002027991447164421080590166911130116483359749418047307595497010369457711350953018694479942850146580996402187310635505278301929397030213544531068769667892360925519410013180703331321321833900350008776368272790481252519169303988218210095146759870287941250090204506960847016059468728275311477613271084474766715488264771177830115028195215223644336345646870679050787515340804351339449474385172464387868299006904638274425855008729765086091731260299397062138670321522563954731398813138738073326593694555049353805161855854036423870334342280080335804850998490793742536882308453307029152812821729798744074167237835462214043679643723245065093600037959124662392297413473130606861784229249604290090458912391096328362137163951398211801143455350336317188806956746282700489013366856863803112203078858200161688528939040348825835610989725020068306497091337571398894447440161081470240965873628208205669354804691958270783090585006358905094926094885655359774269830169287513005586562246433405044654325439410730648108371520856384706590593 + 1/839018826833450186636781520007011999269820404906753180244759299287837378895397605613261469995626498719289835112392530430840514102146998625666594756995273418015600023494049208108894185781774002683063204252356172520941088783702738286944210460710059319691268110283467445381026653628599765684739105388642310044785844902157076919003735231543781785073393176144167688252446541416466418608465458502997971425428342769433127784560570193376772878336217849260872114137931351960543608384244009505664253173875705234889570853924105640193619301332776989688248555027054395237907581951261868280899150574360164800187964167274323078311078867593844043149124596271281252530924719121766925749760855109100066731841478262812686642693395896229983745226277793055820609058348269152190083695704685769622011655159174272326647342695589818127126303038171968768650476413027459205291075571637957597356820188031655122749743652301268394542123970892422944335857917641636041892192547135178153602038877677614358281581103685526041329841496863410305888255234495015115912388514981113593387572720476744188169200130515719608747338810136728267784013352396910979904545913458536243327311977805126410065576961237640824852114328884086581542091492600312838425666927627674227053793897767395465326589843035773944346372949759909905561209334216847158156644884281300512699910530092870919061876615770708519243818676366245477462042294267674677954783726990349386117468071932874021023714524610740225814235147693954027910741673103980749749728106483987721602738673173009362802337092908847797499475895347112889339502928407808058670297722175686638678788738689803945574002805677250463286479363670076942509109589495377221095405979217163821481666646160815221224686562530536116613645305335922819524037829878961518170177968768364853399057357772141655622381280196908637031556436461404285930426436983658106288733881761514992109680298995922754466040011586713812553117621857109517258943846004179432521131844156242428351270188803919554398620084668514054504414062276012292497375238210886595006249453460414790147611422121782194848803348777061816460876697945418158442269512987729152441940326466631610424906158237288218706447963113019239557885486647314085357651895226117364760315394354624547919209138539180807829672545924239541758108877100331729470119526373928796447673951888289511964811633025369821156695934557103429921063387965046715070102916811976552584464153981214277622597308113449320462341683055200576571910241686615924531368198770946893858410058348221985603151428153382461711196734214085852523778422630907646235900752317571022131569421231196329080023952364788544301495422061066036911772385739659997665503832444529713544286955548310166168837889046149061296461059432238621602179724809510024772127497080258401694929973105184832214622785679651550368465524821062859837409907538269572622296774545103747438431266995525592705 = 36/457

PARI/GP[edit]

 
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("]");
best(n)=my(denom,denomAt,term,termAt,v); for(a=1,n-1,for(b=a+1,n, v=efrac(a/b); if(#v>term, termAt=a/b; term=#v); if(v[#v]>denom, denomAt=a/b; denom=v[#v]))); print("Most terms is "termAt" with "term); print("Biggest denominator is "denomAt" with "denom)
apply(show, [43/48, 5/121, 2014/59]);
best(9)
best(99)
best(999)
 
Output:
43/48 = [0; 2, 3, 16]
5/121 = [0; 25, 757, 763309, 873960180913, 1527612795642093418846225]
2014/59 = [34; 8, 95, 14947, 670223480]

Most terms is 3/7 with 3
Biggest denominator is 3/7 with 231

Most terms is 8/97 with 8
Biggest denominator is 8/97 with 579504587067542801713103191859918608251030291952195423583529357653899418686342360361798689053273749372615043661810228371898539583862011424993909789665

Most terms is 529/914 with 13
Biggest denominator is 36/457 with 839...705

Perl 6[edit]

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;
Output:
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

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:

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;
Output:
1/2 + 1/3 + 1/4 + 1/6

The list of terms grows exponentially with the value of the fraction, though.

Python[edit]

from fractions import Fraction
from math import ceil
 
class Fr(Fraction):
def __repr__(self):
return '%s/%s' % (self.numerator, self.denominator)
 
def ef(fr):
ans = []
if fr >= 1:
if fr.denominator == 1:
return [[int(fr)], Fr(0, 1)]
intfr = int(fr)
ans, fr = [[intfr]], fr - intfr
x, y = fr.numerator, fr.denominator
while x != 1:
ans.append(Fr(1, ceil(1/fr)))
fr = Fr(-y % x, y* ceil(1/fr))
x, y = fr.numerator, fr.denominator
ans.append(fr)
return ans
 
if __name__ == '__main__':
for fr in [Fr(43, 48), Fr(5, 121), Fr(2014, 59)]:
print('%r ─► %s' % (fr, ' '.join(str(x) for x in ef(fr))))
lenmax = denommax = (0, None)
for fr in set(Fr(a, b) for a in range(1,100) for b in range(1, 100)):
e = ef(fr)
#assert sum((f[0] if type(f) is list else f) for f in e) == fr, 'Whoops!'
elen, edenom = len(e), e[-1].denominator
if elen > lenmax[0]:
lenmax = (elen, fr, e)
if edenom > denommax[0]:
denommax = (edenom, fr, e)
print('Term max is %r with %i terms' % (lenmax[1], lenmax[0]))
dstr = str(denommax[0])
print('Denominator max is %r with %i digits %s...%s' %
(denommax[1], len(dstr), dstr[:5], dstr[-5:]))
Output:
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

Racket[edit]

#lang racket
(define (real->egyptian-list R)
(define (inr r rv)
(match* ((exact-floor r) (numerator r) (denominator r))
[(0 0 1) (reverse rv)]
[(0 1 d) (reverse (cons (/ d) rv))]
[(0 x y) (let ((^y/x (exact-ceiling (/ y x))))
(inr (/ (modulo (- y) x) (* y ^y/x)) (cons (/ ^y/x) rv)))]
[(flr _ _) (inr (- r flr) (cons flr rv))]))
(inr R null))
 
(define (real->egyptian-string f)
(define e.f.-list (real->egyptian-list f))
(define fmt-part
(match-lambda
[(? integer? (app number->string s)) s]
[(app (compose number->string /) s) (format "/~a"s)]))
(string-join (map fmt-part e.f.-list) " + "))
 
(define (stat-egyptian-fractions max-b+1)
(define-values (max-l max-l-f max-d max-d-f)
(for*/fold ((max-l 0) (max-l-f #f) (max-d 0) (max-d-f #f))
((b (in-range 1 max-b+1)) (a (in-range 1 b)) #:when (= 1 (gcd a b)))
(define f (/ a b))
(define e.f (real->egyptian-list (/ a b)))
(define l (length e.f))
(define d (denominator (last e.f)))
(values (max max-l l) (if (> l max-l) f max-l-f)
(max max-d d) (if (> d max-d) f max-d-f))))
(printf #<<EOS
max #terms: ~a has ~a
[~.a]
max denominator: ~a has ~a
[~.a]
 
EOS
max-l-f max-l (real->egyptian-string max-l-f)
max-d-f max-d (real->egyptian-string max-d-f)))
 
(displayln (real->egyptian-string 43/48))
(displayln (real->egyptian-string 5/121))
(displayln (real->egyptian-string 2014/59))
(newline)
(stat-egyptian-fractions 100)
(newline)
(stat-egyptian-fractions 1000)
 
(module+ test (require tests/eli-tester)
(test (real->egyptian-list 43/48) => '(1/2 1/3 1/16)))
Output:

(Line continuations have been manually added to this "post-production")

/2 + /3 + /16
/25 + /757 + /763309 + /873960180913 + /1527612795642093418846225
34 + /8 + /95 + /14947 + /670223480

max #terms: 44/53 has 8
[/2 + /4 + /13 + /307 + /120871 + /20453597227 + /697249399186783218655 + /1458\
470173998990524806872692984177836808420]
max denominator: 8/97 has 57950458706754280171310319185991860825103029195219542\
3583529357653899418686342360361798689053273749372615043661810228371898539583862\
011424993909789665
[/13 + /181 + /38041 + /1736503177 + /3769304102927363485 + /189435378937934085\
04192074528154430149 + /5382864419003802113658172851049070863474397461302269732\
53778132494225813153 + /5795045870675428017131031918599186082510302919521954235\
83529357653...]

max #terms: 641/796 has 13
[/2 + /4 + /19 + /379 + /159223 + /28520799973 + /929641178371338400861 + /1008\
271507277592391123742528036634174730681 + /121993371886539365536463536806812475\
6713122928811333803786753398211072842948484537833 + /18602978480309366547426083\
99135821395...]
max denominator: 36/457 has 839018826833450186636781520007011999269820404906753\
1802447592992878373788953976056132614699956264987192898351123925304308405141021\
4699862566659475699527341801560002349404920810889418578177400268306320425235617\
2520941088783702738286944210460710059319691268110283467445381026653628599765684\
7391053886423100447858449021570769190037352315437817850733931761441676882524465\
4141646641860846545850299797142542834276943312778456057019337677287833621784926\
0872114137931351960543608384244009505664253173875705234889570853924105640193619\
3013327769896882485550270543952379075819512618682808991505743601648001879641672\
7432307831107886759384404314912459627128125253092471912176692574976085510910006\
6731841478262812686642693395896229983745226277793055820609058348269152190083695\
7046857696220116551591742723266473426955898181271263030381719687686504764130274\
5920529107557163795759735682018803165512274974365230126839454212397089242294433\
5857917641636041892192547135178153602038877677614358281581103685526041329841496\
8634103058882552344950151159123885149811135933875727204767441881692001305157196\
0874733881013672826778401335239691097990454591345853624332731197780512641006557\
6961237640824852114328884086581542091492600312838425666927627674227053793897767\
3954653265898430357739443463729497599099055612093342168471581566448842813005126\
9991053009287091906187661577070851924381867636624547746204229426767467795478372\
6990349386117468071932874021023714524610740225814235147693954027910741673103980\
7497497281064839877216027386731730093628023370929088477974994758953471128893395\
0292840780805867029772217568663867878873868980394557400280567725046328647936367\
0076942509109589495377221095405979217163821481666646160815221224686562530536116\
6136453053359228195240378298789615181701779687683648533990573577721416556223812\
8019690863703155643646140428593042643698365810628873388176151499210968029899592\
2754466040011586713812553117621857109517258943846004179432521131844156242428351\
2701888039195543986200846685140545044140622760122924973752382108865950062494534\
6041479014761142212178219484880334877706181646087669794541815844226951298772915\
2441940326466631610424906158237288218706447963113019239557885486647314085357651\
8952261173647603153943546245479192091385391808078296725459242395417581088771003\
3172947011952637392879644767395188828951196481163302536982115669593455710342992\
1063387965046715070102916811976552584464153981214277622597308113449320462341683\
0552005765719102416866159245313681987709468938584100583482219856031514281533824\
6171119673421408585252377842263090764623590075231757102213156942123119632908002\
3952364788544301495422061066036911772385739659997665503832444529713544286955548\
3101661688378890461490612964610594322386216021797248095100247721274970802584016\
9492997310518483221462278567965155036846552482106285983740990753826957262229677\
4545103747438431266995525592705
[/13 + /541 + /321409 + /114781617793 + /14821672255960844346913 + /25106510681\
4993628596500876449600804290086881 + /73539302503361520198362339236500915390885\
795679264404865887253300925727812630083326272641 + /648963481521709674175890714\
89823812369...]
1 test passed

REXX[edit]

/*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.*/
return z /*stick a fork in it, we're done.*/
/*────────────────────────────────$EGYPTF subroutine──────────────────────────*/
$egyptF: parse arg z 1 zn '/' zd,,$; if zd=='' then zd=1 /*whole number ?*/
if z='' then call erx "no fraction was specified."
if zd==0 then call erx "denominator can't be zero:" zd
if zn==0 then call erx "numerator can't be zero:" zn
if zd<0 | zn<0 then call erx "fraction can't be negative" z
if \datatype(zn,'W') then call erx "numerator must be an integer:" zn
if \datatype(zd,'W') then call erx "denominator must be an integer:" zd
_=zn%zd /*check if it's an improper fraction. */
if _>=1 then do /*if improper fraction, then append it.*/
$='['_"]" /*append the whole # part of fraction. */
zn=zn-_*zd /*now, just use the proper fraction. */
if zn==0 then return $ /*Is there no fraction? Then we're done*/
end
if zd//zn==0 then do; zd=zd%zn; zn=1; end
do forever
if zn==1 & datatype(zd,'W') then return $ "1/"zd /*append Egyptian fract.*/
nd=zd%zn+1; $=$ '1/'nd /*add unity to integer fraction, append*/
z=$fractSub(zn'/'zd, "-", 1'/'nd) /*go and subtract the two fractions. */
parse var z zn '/' zd /*extract the numerator and denominator*/
L=2*max(length(zn),length(zd)) /*calculate if need more decimal digits*/
if L>=digits() then numeric digits L+L /*yes, then bump the decimal digits*/
end /*forever*/ /* [↑] the DO forever ends when zn==1.*/
/*────────────────────────────────$FRACTSUB subroutine────────────────────────*/
$fractSub: procedure; parse arg z.1,,z.2 1 zz.2; arg ,op
do j=1 for 2; z.j=translate(z.j,'/',"_"); end
if z.1=='' then z.1=(op\=="+" & op\=='-') /*unary +,- first fraction.*/
if z.2=='' then z.2=(op\=="+" & op\=='-') /*unary +.- second fraction.*/
do j=1 for 2 /*process both of the fractions*/
if pos('/',z.j)==0 then z.j=z.j"/1"; parse var z.j n.j '/' d.j
if \datatype(n.j,'N') then call erx "numerator isn't an integer:" n.j
if \datatype(d.j,'N') then call erx "denominator isn't an integer:" d.j
n.j=n.j/1; d.j=d.j/1 /*normalize numerator/denominator.*/
 
do while \datatype(n.j,'W'); n.j=n.j*10/1; d.j=d.j*10/1; end /*while*/
/* [↑] normalize both numbers. */
if d.j=0 then call erx "denominator can't be zero:" z.j
g=gcd(n.j,d.j); if g=0 then iterate; n.j=n.j/g; d.j=d.j/g
end /*j*/
l=lcm(d.1 d.2); do j=1 for 2; n.j=l*n.j/d.j; d.j=l; end /*j*/
if op=='-' then n.2=-n.2
t=n.1+n.2; u=l; if t==0 then return 0
g=gcd(t,u); t=t/g; u=u/g; if u==1 then return t
return t'/'u
/*─────────────────────────────general 1─line subs────────────────────────────*/
erx: say; say '***error!***' arg(1); say; exit 13
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:   43/48


43/48  ───►   1/2 1/3 1/16

output when the input used is:   5/121

5/121  ───►   1/25 1/757 1/763309 1/873960180913 1/1527612795642093418846225

output when the input used is:   2014/59

2014/59  ───►   [34] 1/8 1/95 1/14947 1/670223480

The following is a driver program to address the requirements to find the largest number of terms for a
1- or 2-digit integer, and the largest denominator.

Also, the same program is used for the 1-, 2-, and 3-digit extra credit task.

/*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.*/
oTop=top; top=abs(top) /*oTop used as a flag to display maxD. */
maxT=0; maxD=0; bigD=; bigT= /*initialize some REXX variables. */
/* [↓] determine biggest andlongest. */
do n=2 to top /*traipse through the numerators. */
do d=n+1 to top /* " " " denominators */
fract=n'/'d /*create the fraction to be used. */
y='EGYPTIAN'(fract||.) /*invoke the REXX program EGYPTIAN.REX*/
t=words(y) /*number of terms in Egyptian fraction.*/
if t>maxT then bigT=fract /*is this a new high for number terms? */
maxT=max(maxT,T) /*find the maximum number of terms. */
b=substr(word(y,t),3) /*get denominator from Egyptian fract. */
if b>maxD then bigD=fract /*is this a new denominator high ? */
maxD=max(maxD,b) /*find the maximum denominator. */
end /*d*/ /* [↑] only use proper fractions. */
end /*n*/ /* [↑] ignore the 1/n fractions. */
/* [↑] display the longest and biggest*/
@= 'in the Egyptian fractions used is' /*literal is used to make a shorter SAY*/
say 'largest number of terms' @ maxT "terms for" bigT
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:

largest number of terms in the Egyptian fractions used is 8 terms for 8/97
largest denominator in the Egyptian fractions is 150 digits is for 8/97
579504587067542801713103191859918608251030291952195423583529357653899418686342360361798689053273749372615043661810228371898539583862011424993909789665

output   for all 1-, 2-, and 3-digit integers when using for input:   -999

largest number of terms in the Egyptian fractions used is 13 terms for 529/914
largest denominator in the Egyptian fractions is 2847 digits is for 36/457

Ruby[edit]

Translation of: Python
def ef(fr)
ans = []
if fr >= 1
return [[fr.to_i], Rational(0, 1)] if fr.denominator == 1
intfr = fr.to_i
ans, fr = [intfr], fr - intfr
end
x, y = fr.numerator, fr.denominator
while x != 1
ans << Rational(1, (1/fr).ceil)
fr = Rational(-y % x, y * (1/fr).ceil)
x, y = fr.numerator, fr.denominator
end
ans << fr
end
 
for fr in [Rational(43, 48), Rational(5, 121), Rational(2014, 59)]
puts '%s => %s' % [fr, ef(fr).join(' + ')]
end
 
lenmax = denommax = [0]
for b in 2..99
for a in 1...b
fr = Rational(a,b)
e = ef(fr)
elen, edenom = e.length, e[-1].denominator
lenmax = [elen, fr] if elen > lenmax[0]
denommax = [edenom, fr] if edenom > denommax[0]
end
end
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
Output:
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 44/53 with 8 terms
Denominator max is 8/97 with 150 digits
579504587067542801713103191859918608251030291952195423583529357653899418686342360361798689053273749372615043661810228371898539583862011424993909789665

Sidef[edit]

Translation of: Ruby
func ef(fr) {
var ans = []
if (fr >= 1) {
return([fr]) if (fr.is_int)
var intfr = fr.to_i
ans << intfr
fr -= intfr
}
var (x, y) = fr.parts
while (x != 1) {
ans << fr.inv.ceil.inv
fr = ((-y % x) / y*fr.inv.ceil)
(x, y) = fr.parts
}
ans << fr
return ans
}
 
for fr in [43/48, 5/121, 2014/59] {
"%s => %s\n".printf(fr.as_rat, ef(fr).map{.as_rat}.join(' + '))
}
 
var lenmax = (var denommax = [0])
for b in range(2, 99) {
for a in range(1, b-1) {
var fr = a/b
var e = ef(fr)
var (elen, edenom) = (e.length, e[-1].denominator)
lenmax = [elen, fr] if (elen > lenmax[0])
denommax = [edenom, fr] if (edenom > denommax[0])
}
}
 
"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]
Output:
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 44/53 with 8 terms
Denominator max is 8/97 with 150 digits
579504587067542801713103191859918608251030291952195423583529357653899418686342360361798689053273749372615043661810228371898539583862011424993909789665

Tcl[edit]

# Just compute the denominator terms, as the numerators are always 1
proc egyptian {num denom} {
set result {}
while {$num} {
# Compute ceil($denom/$num) without floating point inaccuracy
set term [expr {$denom / $num + ($denom/$num*$num < $denom)}]
lappend result $term
set num [expr {-$denom % $num}]
set denom [expr {$denom * $term}]
}
return $result
}

Demonstrating:

Works with: Tcl version 8.6
package require Tcl 8.6
 
proc efrac {fraction} {
scan $fraction "%d/%d" x y
set prefix ""
if {$x > $y} {
set whole [expr {$x / $y}]
set x [expr {$x - $whole*$y}]
set prefix "\[$whole\] + "
}
return $prefix[join [lmap y [egyptian $x $y] {format "1/%lld" $y}] " + "]
}
 
foreach f {43/48 5/121 2014/59} {
puts "$f = [efrac $f]"
}
set maxt 0
set maxtf {}
set maxd 0
set maxdf {}
for {set d 1} {$d < 100} {incr d} {
for {set n 1} {$n < $d} {incr n} {
set e [egyptian $n $d]
if {[llength $e] >= $maxt} {
set maxt [llength $e]
set maxtf $n/$d
}
if {[lindex $e end] > $maxd} {
set maxd [lindex $e end]
set maxdf $n/$d
}
}
}
puts "$maxtf has maximum number of terms = [efrac $maxtf]"
puts "$maxdf has maximum denominator = [efrac $maxdf]"
Output:
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 maximum number of terms = 1/13 + 1/181 + 1/38041 + 1/1736503177 + 1/3769304102927363485 + 1/18943537893793408504192074528154430149 + 1/538286441900380211365817285104907086347439746130226973253778132494225813153 + 1/579504587067542801713103191859918608251030291952195423583529357653899418686342360361798689053273749372615043661810228371898539583862011424993909789665
8/97 has maximum denominator = 1/13 + 1/181 + 1/38041 + 1/1736503177 + 1/3769304102927363485 + 1/18943537893793408504192074528154430149 + 1/538286441900380211365817285104907086347439746130226973253778132494225813153 + 1/579504587067542801713103191859918608251030291952195423583529357653899418686342360361798689053273749372615043661810228371898539583862011424993909789665

Note also that also has 8 terms.

zkl[edit]

Translation of: Tcl
# Just compute the denominator terms, as the numerators are always 1
fcn egyptian(num,denom){
result,t := List(),Void;
t,num=num.divr(denom); // reduce fraction
if(t) result.append(T(t)); // signal t isn't a denominator
while(num){
# Compute ceil($denom/$num) without floating point inaccuracy
term:=denom/num + (denom/num*num < denom);
result.append(term);
z:=denom%num;
num=(if(z) num-z else 0);
denom*=term;
}
result
}
fcn efrac(fraction){ // list to string, format list of denominators
fraction.pump(List,fcn(denom){
if(denom.isType(List)) denom[0]
else String("1/",denom);
}).concat(" + ")
}
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(_)));
}
Output:
43/48 --> 1/2 + 1/3 + 1/16
5/121 --> 1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1025410058030422033
2014/59 --> 34 + 1/8 + 1/95 + 1/14947 + 1/670223480

For the big denominators, use GMP (Gnu Multi Precision).

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
e,eLen,eDenom := egyptian(BN(n),BN(d)), e.len(), e[-1];
if(eDenom.isType(List)) eDenom=1;
if(eLen >lenMax[0]) lenMax.clear(eLen,T(n,d));
if(eDenom>denomMax[0]) denomMax.clear(eDenom,T(n,d));
}
println("Term max is %s/%s with %d terms".fmt(lenMax[1].xplode(), lenMax[0]));
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,*]));
Output:
Term max is 97/53 with 9 terms
Denominator max is 8/97 with 150 digits 57950...89665