Skip to content

Instantly share code, notes, and snippets.

@utgwkk

utgwkk/egypt_frac.py

Created Feb 23, 2014
Embed
What would you like to do?
Calculate Egyptian fraction
def getdiv(n):
l = []
for k in xrange(1,n):
if n%k==0: l.append(k)
return l
def go(l,n,m):
l = [[x,0] for x in l if x/m <= 0.5]
f = [0 for x in xrange(len(l))]
for i in xrange(2**len(f)-1):
a = [l[x][f[x]] for x in xrange(len(l))]
if sum(a) == n:
return [x for x in a if x != 0]
f[0] += 1
for j in xrange(len(f)):
if f[j] > 1:
f[j] = 0
f[j+1] += 1
return False
a = int(raw_input('D > ').rstrip())
b = int(raw_input('N > ').rstrip())
print '%d/%d ='%(b,a),
d = 1
while True:
c = go(getdiv(a*d),b*d,a*d)
if c:
print ' + '.join(['1/%d'%(a*d/x) for x in c])
break
d += 1
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.