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