Greedy algorithm for Egyptian fractions: Difference between revisions

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

<lang common lisp>(defun egyption-fractions (x y &optional acc)

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

(cond

((> (numerator a) (denominator a))

(multiple-value-bind (q r) (floor x y)

(if (zerop r)

(cons q acc)

(egyption-fractions r y (cons q acc)))))

((= (numerator a) 1) (reverse (cons a acc)))

(t (let ((b (1+ (floor y x))))

(egyption-fractions (mod (- y) x) (* y b) (cons (/ b) acc)))))))

(defun test (n fn)

(car (sort (loop for i from 1 to n append

(loop for j from 2 to n collect

(cons (/ i j) (funcall fn (egyption-fractions i j)))))

#'>

:key #'cdr)))

</lang>

{{out}}

<pre>(egyption-fractions 43 48)

(egyption-fractions 5 121)

(egyption-fractions 2014 59)

(egyption-fractions 8 97)

</pre>

Basic tests:

<pre>(1/2 1/3 1/16)

(1/25 1/757 1/763309 1/873960180913 1/1527612795642093418846225)

(34 1/8 1/95 1/14947 1/670223480)

(1/13 1/181 1/38041 1/1736503177 1/3769304102927363485

1/18943537893793408504192074528154430149

1/538286441900380211365817285104907086347439746130226973253778132494225813153

1/579504587067542801713103191859918608251030291952195423583529357653899418686342360361798689053273749372615043661810228371898539583862011424993909789665)

</pre>

Other tests:

<pre>(test 999 #'length)

(test 999 (lambda (xs) (loop for x in xs maximizing (denominator x))))

</pre>

<pre>(493/457 . 13)

(36/457

. 839018826833450186636781520007011999269820404906753180244759299287837378895397605613261469995626498719289835112392530430840514102146998625666594756995273418015600023494049208108894185781774002683063204252356172520941088783702738286944210460710059319691268110283467445381026653628599765684739105388642310044785844902157076919003735231543781785073393176144167688252446541416466418608465458502997971425428342769433127784560570193376772878336217849260872114137931351960543608384244009505664253173875705234889570853924105640193619301332776989688248555027054395237907581951261868280899150574360164800187964167274323078311078867593844043149124596271281252530924719121766925749760855109100066731841478262812686642693395896229983745226277793055820609058348269152190083695704685769622011655159174272326647342695589818127126303038171968768650476413027459205291075571637957597356820188031655122749743652301268394542123970892422944335857917641636041892192547135178153602038877677614358281581103685526041329841496863410305888255234495015115912388514981113593387572720476744188169200130515719608747338810136728267784013352396910979904545913458536243327311977805126410065576961237640824852114328884086581542091492600312838425666927627674227053793897767395465326589843035773944346372949759909905561209334216847158156644884281300512699910530092870919061876615770708519243818676366245477462042294267674677954783726990349386117468071932874021023714524610740225814235147693954027910741673103980749749728106483987721602738673173009362802337092908847797499475895347112889339502928407808058670297722175686638678788738689803945574002805677250463286479363670076942509109589495377221095405979217163821481666646160815221224686562530536116613645305335922819524037829878961518170177968768364853399057357772141655622381280196908637031556436461404285930426436983658106288733881761514992109680298995922754466040011586713812553117621857109517258943846004179432521131844156242428351270188803919554398620084668514054504414062276012292497375238210886595006249453460414790147611422121782194848803348777061816460876697945418158442269512987729152441940326466631610424906158237288218706447963113019239557885486647314085357651895226117364760315394354624547919209138539180807829672545924239541758108877100331729470119526373928796447673951888289511964811633025369821156695934557103429921063387965046715070102916811976552584464153981214277622597308113449320462341683055200576571910241686615924531368198770946893858410058348221985603151428153382461711196734214085852523778422630907646235900752317571022131569421231196329080023952364788544301495422061066036911772385739659997665503832444529713544286955548310166168837889046149061296461059432238621602179724809510024772127497080258401694929973105184832214622785679651550368465524821062859837409907538269572622296774545103747438431266995525592705)

</pre>