Check out the Pastebin Gadgets Shop. We have thousands of fun, geeky & affordable gadgets on sale :-)Want more features on Pastebin? Sign Up, it's FREE!

# egyptian fractions

By: phillip1882 on Jun 5th, 2013  |  syntax: Python  |  size: 1.41 KB  |  views: 86  |  expires: Never
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
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)
clone this paste RAW Paste Data
Top