Greedy algorithm for Egyptian fractions: Difference between revisions
Greedy algorithm for Egyptian fractions (view source)
Revision as of 02:36, 13 January 2020
, 4 years ago→{{header|Fōrmulæ}}
mNo edit summary |
|||
Line 680:
Largest size for denominator is 2847 for 36/457, 529/914</pre>
=={{header|Frink}}==
<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"]
}
</lang>
{{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æ}}==
| |||