Greedy algorithm for Egyptian fractions: Difference between revisions

;Also see:

*   Wolfram MathWorld™ entry: [http://mathworld.wolfram.com/EgyptianFraction.html Egyptian fraction]

<br><br>

 

Based on the VB.NET sample.<br>

Uses Algol 68G's LONG LONG INT for large integers.

PR precision 2000 PR # set the number of digits for LONG LONG INT #

PROC gcd = ( LONG LONG INT a, b )LONG LONG INT:

)

END

{{out}}

<pre>

=={{header|C}}==

Output has limited accuracy as noted by comments. The problem requires bigint support to be completely accurate.

#include <stdint.h>

#include <stdio.h>

 

return 0;

{{out}}

<pre>Egyptian fraction for 43/48: 1/2 + 1/3 + 1/16

=={{header|C sharp|C#}}==

{{trans|Visual Basic .NET}}

using System.Collections.Generic;

using System.Linq;

}

}

{{out}}

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

{{libheader|Boost}}

The C++ standard library does not have a "big integer" type, so this solution uses the Boost library.

#include <sstream>

 

typedef boost::multiprecision::cpp_int integer;

 

 

size_t count_digits(const integer& i) {

}

 

const int max_digits = 20;

std::ostringstream os;

os << i;

std::string s = os.str();

return s;

}

 

result.clear();

while (x > 0) {

x = mod(-y, x);

y = y * z;

}

 

if (result.empty())

return;

auto i = result.begin();

for (; i != result.end(); ++i)

}

 

if (x > y) {

x = x % y;

}

print_egyptian(result);

}

 

void show_max_terms_and_max_denominator(const integer& limit) {

size_t max_terms = 0;

integer max_denominator = 0;

for (integer b = 2; b < limit; ++b) {

for (integer a = 1; a < b; ++a) {

if (result.size() > max_terms) {

max_terms = result.size();

max_terms_result = result;

}

max_denominator_result = result;

}

}

}

print_egyptian(max_terms_result);

print_egyptian(max_denominator_result);

}

 

int main() {

show_max_terms_and_max_denominator(100);

show_max_terms_and_max_denominator(1000);

return 0;

 

{{out}}

 

Largest denominator (150 digits): 8/97 = 1/13 + 1/181 + 1/38041 + 1/1736503177 + 1/3769304102927363485 + 1/1894353789...8154430149 + 1/5382864419...4225813153 + 1/5795045870...3909789665

Proper fractions with most terms and largest denominator, limit = 1000:

 

 

Largest denominator (2847 digits): 36/457 = 1/13 + 1/541 + 1/321409 + 1/114781617793 + 1/1482167225...0844346913 + 1/2510651068...4290086881 + 1/7353930250...3326272641 + 1/6489634815...7391865217 + 1/5264420004...5476206145 + 1/3695215730...1238141889 + 1/2048192894...4706590593 + 1/8390188268...5525592705

</pre>

 

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

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

(cond

#'>

: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

 

=={{header|Erlang}}==

 

-import(lists, [reverse/1, seq/2]).

true -> B

end.

 

{{out}}

</pre>

 

=={{header|Factor}}==

math.functions math.ranges sequences ;

IN: rosetta-code.egyptian-fractions

: egyptian-fractions-demo ( -- ) part1 part2 ;

 

{{out}}

<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

 

=={{header|Frink}}==

frac[p, q] :=

{

println["The fraction with the largest denominator is $biggest"]

}

{{Out}}

<pre>

=={{header|Fōrmulæ}}==

 

 

 

 

=={{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''':

λ> quickCheck (\n -> n == (sum $ egyptianFraction n))

 

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

{{trans|Go}}

{{libheader|bignum}}

import bignum

 

let md = $maxDen

echo fmt" largest denominator = {md.len} digits, {md[0..19]}...{md[^20..^1]}"

 

{{out}}

 

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

 

=={{header|Perl}}==

use warnings;

use bigint;

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

isEgyption($nrI,$deI);

{{out}}

<pre>

{{libheader|Phix/mpfr}}

The sieve copied from Go

{{out}}

<pre>

=={{header|Prolog}}==

{{works with|SWI Prolog}}

atom_number(A, Number),

atom_length(A, Count).

show_max_terms_and_denominator(100),

nl,

 

{{out}}

=={{header|Python}}==

===Procedural===

from math import ceil

 

dstr = str(denommax[0])

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

 

{{out}}

See the '''unfoldr''' function below:

{{Works with|Python|3.7}}

 

from fractions import Fraction

# MAIN ---

if __name__ == '__main__':

{{Out}}

<pre>Three values as Eqyptian fractions:

=={{header|Racket}}==

 

(define (real->egyptian-list R)

(define (inr r rv)

 

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

 

{{out}}

=={{header|Raku}}==

(formerly Perl 6)

method gist {

join ' + ',

" has max number of denominators, namely ",

.value.elems

{{out}}

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

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:

 

method gist { join ' + ', map {"1/$_"}, self.list }

method list {

}

{{out}}

<pre>1/2 + 1/3 + 1/4 + 1/6</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}}

 

=={{header|Rust}}==

use num_bigint::BigInt;

use num_integer::Integer;

}

 

{{out}}

<pre>

=={{header|Scala}}==

{{trans|Java}}

import scala.collection.mutable

import scala.collection.mutable.{ArrayBuffer, ListBuffer}

}

}

{{out}}

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

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

=={{header|Visual Basic .NET}}==

{{trans|D}}

Imports System.Text

 

End Sub

 

{{out}}

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

{{libheader|Wren-big}}

We use the BigRat class in the above module to represent arbitrary size fractions.

 

var toEgyptianHelper // recursive

System.print("%(md[0...20])...%(md[-20..-1])")

System.print(" fraction(s) with this denominator : %(maxDenFracs)")

 

{{out}}

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