Advertisement
phillip1882

egyptian fractions

Jun 5th, 2013
189
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.41 KB | None | 0 0
  1. import math
  2. def factor(b):
  3.    facts = []
  4.    i = 2
  5.    while i <= math.sqrt(b):
  6.       if b%i == 0:
  7.          facts += [i,b/i]
  8.       i += 1
  9.    return facts
  10. def egypt(a,b):
  11.   fraction = []
  12.   F = factor(b)
  13.   G = factor(a)
  14.   i = 0
  15.   while i < len(G):
  16.      if G[i] in F:
  17.         b = b/G[i]
  18.         a = a/G[i]
  19.         F = factor(b)
  20.         G = factor(a)
  21.         i = 0
  22.      i += 1
  23.   i = len(F)-1
  24.   if i <= 0:
  25.      if b/a < 2:
  26.         mult = 2
  27.      else:
  28.         mult = (int(b/a)+1)
  29.      a = mult*a
  30.      b = mult*b
  31.      F = factor(b)
  32.      i = len(F)-1
  33.      #print a,b,F
  34.   temp = []
  35.   temp2 = 0
  36.   while a > 1:
  37.      temp += [a]
  38.      while i >= 0:
  39.        #print a,F[i]
  40.        if a >= F[i] and not b/F[i] in fraction:
  41.           a = a-F[i]
  42.           temp2 = F[i]
  43.           fraction += [b/F[i]]
  44.        i-=1
  45.      if a <= 1 or (b%a == 0 and b/a not in fraction):
  46.         if a > 1:
  47.            fraction += [b/a]
  48.            a = 0
  49.         break
  50.      i+= 1
  51.      while i < len(F) and F[i] <= a:
  52.        i += 1
  53.  
  54.      if i == len(F) or F[i]/a < 2:
  55.         mult = 2
  56.         while a*mult in temp or mult == temp2:
  57.            mult +=1
  58.      else:
  59.         mult = int(F[i]/a)+1
  60.         if mult == temp2:
  61.            mult += 1
  62.      a *= mult
  63.      b *= mult
  64.      F = factor(b)
  65.      i = len(F)-1
  66.      #print fraction,b
  67.      #raw_input()
  68.   if a == 1:
  69.      fraction += [b]
  70.   print fraction
  71.          
  72. egypt(25,37)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement