Greedy algorithm for Egyptian fractions: Difference between revisions

{{task}}

 

 

 

 

 

 

<!--

This Rosetta Code task will be using the Fibonacci greedy algorithm for computing Egyptian fractions; however, if different method is used instead, please note which method is being employed. &nbsp; Having all the programming examples use the Fibonacci greedy algorithm will make for easier comparison and compatible results.

-->

 

 

 

(See the [[#REXX|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 <tt>[''n'']</tt>.

 

;Task requirements:

 

;Also see:

<br><br>

 

=={{header|Common Lisp}}==

(let* ((a (/ x y)))

(cond

#'>

:key #'cdr)))

 

{{out}}

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;

 

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

Term max is 97/53 with 9 terms

Denominator max is 8/97 with 150 digits 57950...89665</pre>

=={{header|FreeBASIC}}==

{{libheader|GMP}}

' compile with: fbc -s console

 

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre>43/48 = 1/2 + 1/3 + 1/16

Largest number of terms is 13 for 641/796, 529/914

Largest size for denominator is 2847 for 36/457, 529/914</pre>

 

=={{header|Go}}==

{{trans|Kotlin}}

... except that Go already has support for arbitrary precision rational numbers in its standard library.

 

import (

fmt.Println(" fraction(s) with this denominator :", maxDenFracs)

}

 

{{out}}

 

=={{header|Haskell}}==

 

egyptianFraction :: Integral a => Ratio a -> [Ratio a]

x = numerator n

y = denominator n

 

'''Testing''':

 

'''Tasks''':

import Data.Ord (comparing)

 

| a <- [1 .. n]

, b <- [1 .. n]

 

43 % 48 = 1 % 2 + 1 % 3 + 1 % 16

5 % 121 = 1 % 25 + 1 % 757 + 1 % 763309 + 1 % 873960180913 + 1 % 1527612795642093418846225

λ> task22 999

(529 % 914, 839018826833450186636781520007011999269820404906753180244759299287837378895397605613261469995626498719289835112392530430840514102146998625666594756995273418015600023494049208108894185781774002683063204252356172520941088783702738286944210460710059319691268110283467445381026653628599765684739105388642310044785844902157076919003735231543781785073393176144167688252446541416466418608465458502997971425428342769433127784560570193376772878336217849260872114137931351960543608384244009505664253173875705234889570853924105640193619301332776989688248555027054395237907581951261868280899150574360164800187964167274323078311078867593844043149124596271281252530924719121766925749760855109100066731841478262812686642693395896229983745226277793055820609058348269152190083695704685769622011655159174272326647342695589818127126303038171968768650476413027459205291075571637957597356820188031655122749743652301268394542123970892422944335857917641636041892192547135178153602038877677614358281581103685526041329841496863410305888255234495015115912388514981113593387572720476744188169200130515719608747338810136728267784013352396910979904545913458536243327311977805126410065576961237640824852114328884086581542091492600312838425666927627674227053793897767395465326589843035773944346372949759909905561209334216847158156644884281300512699910530092870919061876615770708519243818676366245477462042294267674677954783726990349386117468071932874021023714524610740225814235147693954027910741673103980749749728106483987721602738673173009362802337092908847797499475895347112889339502928407808058670297722175686638678788738689803945574002805677250463286479363670076942509109589495377221095405979217163821481666646160815221224686562530536116613645305335922819524037829878961518170177968768364853399057357772141655622381280196908637031556436461404285930426436983658106288733881761514992109680298995922754466040011586713812553117621857109517258943846004179432521131844156242428351270188803919554398620084668514054504414062276012292497375238210886595006249453460414790147611422121782194848803348777061816460876697945418158442269512987729152441940326466631610424906158237288218706447963113019239557885486647314085357651895226117364760315394354624547919209138539180807829672545924239541758108877100331729470119526373928796447673951888289511964811633025369821156695934557103429921063387965046715070102916811976552584464153981214277622597308113449320462341683055200576571910241686615924531368198770946893858410058348221985603151428153382461711196734214085852523778422630907646235900752317571022131569421231196329080023952364788544301495422061066036911772385739659997665503832444529713544286955548310166168837889046149061296461059432238621602179724809510024772127497080258401694929973105184832214622785679651550368465524821062859837409907538269572622296774545103747438431266995525592705)

 

=={{header|J}}==

+-------+--------------------------------------------------------------+

|43r48 |1r2 1r3 1r16 |

+-------+--------------------------------------------------------------+

|2014r59|34 1r8 1r95 1r14947 1r670223480 |

 

EF2 =: ef :: _1:&.> (</~ * %/~) i. 10^2x

 

52971354428695554831016616883788904614906129646105943223862160217972480951002477

21274970802584016949299731051848322146227856796515503684655248210628598374099075

 

=={{header|Java}}==

{{trans|Kotlin}}

{{works with|Java|9}}

import java.math.BigInteger;

import java.math.MathContext;

}

}

{{out}}

<pre>43/48 -> 1/2 + 1/3 + 1/16

{{works with|Julia|0.6}}

 

int::T

frac::NTuple{N,Rational{T}} where N

frlenmax, lenmax, frdenmax, denmax = task(fr)

println("Longest fraction, with length $lenmax: \n", Rational(frlenmax), "\n = ", frlenmax)

 

{{out}}

=={{header|Kotlin}}==

As the JDK lacks a fraction or rational class, I've included a basic one in the program.

 

import java.math.BigInteger

println(" fraction(s) with this denominator : $maxDenFracs")

}

 

{{out}}

</pre>

 

frac[n_] :=

frac[n] =

fracs = Flatten[Table[frac[p/q], {q, 999}, {p, q}], 1];

Print[disp[MaximalBy[fracs, Length@*Union][[1]]]];

{{out}}

<pre>1/2 + 1/3 + 1/16 = 43/48

=={{header|Microsoft Small Basic}}==

Small Basic but large (not huge) integers.

xx=2014

yy=59

EndWhile

ret=wx

{{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|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("]");

best(99)

best(999)

{{out}}

<pre>43/48 = [0; 2, 3, 16]

Most terms is 529/914 with 13

Biggest denominator is 36/457 with 839...705</pre>

=={{header|Perl}}==

use warnings;

use bigint;

printf "\nEgyptian Fraction Representation of " . $nrI . "/" . $deI . " is: \n\n";

isEgyption($nrI,$deI);

{{out}}

<pre>

34 + 1/8 + 1/95 + 1/14947 + 1/670223480

</pre>

 

=={{header|Phix}}==

{{trans|tcl}}

The sieve copied from Go

{{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

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|Python}}==

from math import ceil

 

dstr = str(denommax[0])

print('Denominator max is %r with %i digits %s...%s' %

 

{{out}}

Term max is 97/53 with 9 terms

Denominator max is 8/97 with 150 digits 57950...89665</pre>

 

=={{header|Racket}}==

 

(define (real->egyptian-list R)

(define (inr r rv)

 

(module+ test (require tests/eli-tester)

 

{{out}}

89823812369...]

1 test passed</pre>

 

=={{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.*/

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

'''output''' &nbsp; when the input used is: &nbsp; <tt> 43/48 </tt>

<pre>

 

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.*/

say

say 'highest denominator' @ length(maxD) "digits for" bigD

'''output''' &nbsp; for all 1- and 2-digit integers when using the default input:

<pre>

largest denominator in the Egyptian fractions is 2847 digits is for 36/457

</pre>

 

=={{header|Ruby}}==

{{trans|Python}}

ans = []

if fr >= 1

puts 'Term max is %s with %i terms' % [lenmax[1], lenmax[0]]

dstr = denommax[0].to_s

 

{{out}}

579504587067542801713103191859918608251030291952195423583529357653899418686342360361798689053273749372615043661810228371898539583862011424993909789665

</pre>

 

=={{header|Sidef}}==

{{trans|Ruby}}

var ans = []

if (fr >= 1) {

"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)

{{out}}

<pre>

 

=={{header|Tcl}}==

proc egyptian {num denom} {

set result {}

}

return $result

Demonstrating:

{{works with|Tcl|8.6}}

 

proc efrac {fraction} {

}

puts "$maxtf has maximum number of terms = [efrac $maxtf]"

{{out}}

<pre>

Note also that <math>\tfrac{44}{53}</math> also has 8 terms.

:<math>\tfrac{1}{2} + \tfrac{1}{4} + \tfrac{1}{13} + \tfrac{1}{307} + \tfrac{1}{120871} + \tfrac{1}{20453597227} + \tfrac{1}{697249399186783218655} + \tfrac{1}{1458470173998990524806872692984177836808420}</math>

 

=={{header|zkl}}==

{{trans|Tcl}}

fcn egyptian(num,denom){

result,t := List(),Void;

else String("1/",denom);

}).concat(" + ")

println("%s/%s --> %s".fmt(n,d, egyptian(n,d):efrac(_)));

{{out}}

<pre>

</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

dStr:=denomMax[0].toString();

println("Denominator max is %s/%s with %d digits %s...%s"

{{out}}

<pre>