Greedy algorithm for Egyptian fractions: Difference between revisions

===Procedural===

===Composition of pure functions===

The derivation of a sequence of unit fractions from a single fraction is a classic case of an anamorphism or '''unfold''' abstraction – dual to a fold or catamorphism. Rather than reducing, collapsing or summarizing a structure '''to''' a single value, it builds a structure '''from''' a single value.

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

{{Works with|Python|3.7}}

<lang python>'''Egyptian fractions'''

from fractions import Fraction

from functools import reduce

from operator import neg

# eqyptianFraction :: Ratio Int -> Ratio Int

def eqyptianFraction(nd):

'''The rational number nd as a sum

of the series of unit fractions

obtained by application of the

greedy algorithm.'''

def go(x):

n, d = x.numerator, x.denominator

r = 1 + d // n if n else None

return Just((0, x) if 1 == n else (

(fr(n % d, d), fr(n // d, 1)) if n > d else (

fr(-d % n, d * r), fr(1, r)

)

)) if n else Nothing()

fr = Fraction

xs = unfoldr(go)(nd)

return list(map(neg, xs)) if 0 > nd else xs

# TESTS ---------------------------------------------------

# maxEqyptianFraction :: Int -> (Ratio Int -> a)

# -> (Ratio Int, a)

def maxEqyptianFraction(nDigits):

'''An Egyptian Fraction, representing a

proper fraction with numerators and

denominators of up to n digits each,

which returns a maximal value for the

supplied function f.'''

# maxVals :: ([Ratio Int], a) -> (Ratio Int, a)

# -> ([Ratio Int], a)

def maxima(xsv, ndfx):

xs, v = xsv

nd, fx = ndfx

return ([nd], fx) if fx > v else (

xs + [nd], v

) if fx == v and nd not in xs else xsv

# go :: (Ratio Int -> a) -> ([Ratio Int], a)

def go(f):

iLast = int(nDigits * '9')

fs, mx = reduce(

maxima, [

(nd, f(eqyptianFraction(nd))) for nd in [

Fraction(n, d)

for n in enumFromTo(1)(iLast)

for d in enumFromTo(1 + n)(iLast)

]

],

([], 0)

)

return f.__name__ + ' -> [' + ', '.join(

map(str, fs)

) + '] -> ' + str(mx)

return lambda f: go(f)

# main :: IO ()

def main():

'''Tests'''

ef = eqyptianFraction

fr = Fraction

print('Three values as Eqyptian fractions:')

print('\n'.join([

str(fr(*nd)) + ' -> ' + ' + '.join(map(str, ef(fr(*nd))))

for nd in [(43, 48), (5, 121), (2014, 59)]

]))

# maxDenominator :: [Ratio Int] -> Int

def maxDenominator(ef):

return max(map(lambda nd: nd.denominator, ef))

# maxTermCount :: [Ratio Int] -> Int

def maxTermCount(ef):

return len(ef)

for i in [1, 2, 3]:

print(

'\nMaxima for proper fractions with up to ' + (

str(i) + ' digit(s):'

)

)

for f in [maxTermCount, maxDenominator]:

print(maxEqyptianFraction(i)(f))

# GENERIC -------------------------------------------------

# Just :: a -> Maybe a

def Just(x):

'''Constructor for an inhabited Maybe (option type) value.'''

return {'type': 'Maybe', 'Nothing': False, 'Just': x}

# Nothing :: Maybe a

def Nothing():

'''Constructor for an empty Maybe (option type) value.'''

return {'type': 'Maybe', 'Nothing': True}

# enumFromTo :: (Int, Int) -> [Int]

def enumFromTo(m):

'''Integer enumeration from m to n.'''

return lambda n: list(range(m, 1 + n))

# unfoldr :: (b -> Maybe (b, a)) -> b -> [a]

def unfoldr(f):

'''Dual to reduce or foldr.

Where catamorphism reduces a list to a summary value,

the anamorphic unfoldr builds a list from a seed value.

As long as f returns Just(a, b), a is prepended to the list,

and the residual b is used as the argument for the next

application of f.

When f returns Nothing, the completed list is returned.'''

def go(xr):

mb = f(xr[0])

if mb.get('Nothing'):

return []

else:

y, r = mb.get('Just')

return [r] + go((y, r))

return lambda x: go((x, x))

# MAIN ---

if __name__ == '__main__':

main()</lang>

{{Out}}

<pre>Three values as Eqyptian fractions:

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

5/121 -> 1/25 + 1/757 + 1/763309 + 1/873960180913 + 1/1527612795642093418846225

2014/59 -> 34 + 1/8 + 1/95 + 1/14947 + 1/670223480

Maxima for proper fractions with up to 1 digit(s):

maxTermCount -> [3/7, 4/5, 5/7, 6/7, 7/8, 7/9, 8/9] -> 3

maxDenominator -> [3/7] -> 231

Maxima for proper fractions with up to 2 digit(s):

maxTermCount -> [8/97, 44/53] -> 8

maxDenominator -> [8/97] -> 579504587067542801713103191859918608251030291952195423583529357653899418686342360361798689053273749372615043661810228371898539583862011424993909789665

Maxima for proper fractions with up to 3 digit(s):

maxTermCount -> [529/914, 641/796] -> 13

maxDenominator -> [36/457, 529/914] -> 839018826833450186636781520007011999269820404906753180244759299287837378895397605613261469995626498719289835112392530430840514102146998625666594756995273418015600023494049208108894185781774002683063204252356172520941088783702738286944210460710059319691268110283467445381026653628599765684739105388642310044785844902157076919003735231543781785073393176144167688252446541416466418608465458502997971425428342769433127784560570193376772878336217849260872114137931351960543608384244009505664253173875705234889570853924105640193619301332776989688248555027054395237907581951261868280899150574360164800187964167274323078311078867593844043149124596271281252530924719121766925749760855109100066731841478262812686642693395896229983745226277793055820609058348269152190083695704685769622011655159174272326647342695589818127126303038171968768650476413027459205291075571637957597356820188031655122749743652301268394542123970892422944335857917641636041892192547135178153602038877677614358281581103685526041329841496863410305888255234495015115912388514981113593387572720476744188169200130515719608747338810136728267784013352396910979904545913458536243327311977805126410065576961237640824852114328884086581542091492600312838425666927627674227053793897767395465326589843035773944346372949759909905561209334216847158156644884281300512699910530092870919061876615770708519243818676366245477462042294267674677954783726990349386117468071932874021023714524610740225814235147693954027910741673103980749749728106483987721602738673173009362802337092908847797499475895347112889339502928407808058670297722175686638678788738689803945574002805677250463286479363670076942509109589495377221095405979217163821481666646160815221224686562530536116613645305335922819524037829878961518170177968768364853399057357772141655622381280196908637031556436461404285930426436983658106288733881761514992109680298995922754466040011586713812553117621857109517258943846004179432521131844156242428351270188803919554398620084668514054504414062276012292497375238210886595006249453460414790147611422121782194848803348777061816460876697945418158442269512987729152441940326466631610424906158237288218706447963113019239557885486647314085357651895226117364760315394354624547919209138539180807829672545924239541758108877100331729470119526373928796447673951888289511964811633025369821156695934557103429921063387965046715070102916811976552584464153981214277622597308113449320462341683055200576571910241686615924531368198770946893858410058348221985603151428153382461711196734214085852523778422630907646235900752317571022131569421231196329080023952364788544301495422061066036911772385739659997665503832444529713544286955548310166168837889046149061296461059432238621602179724809510024772127497080258401694929973105184832214622785679651550368465524821062859837409907538269572622296774545103747438431266995525592705</pre>