I feel bad about this one because I knew I needed a greatest common denominator function, but I didn’t have one that I felt was optimal. So I pulled one that I found in the forums and just used that. I mean, I suppose that’s okay, but I still feel bad because I didn’t come up with it all by myself. Either way, it got the job done.
from time import time
start = time(); end = time()
r = []
def gcd(a, b):
while b != 0:
a, b = b, a % b
return abs(a)
def isreduced(x, y):
for i in range(2, x+1):
if x%i == y%i == 0:
return False
return True
def reduce(x, y, r):
x = int(x)
y = int(y)
if (x, y) not in r:
return True
for i in range(2, int(12000/y)+2):
r.append((x*i, y*i))
else:
return False
def divide(x, y):
x = int(x)
y = int(y)
z = []
while len(z) < 10:
if (x / y) >= 1:
z.append(x / y)
x = x%y * 10
else:
x = x*10
z.append(0)
return int(''.join(map(str, z[1:])))
half = float(1) / float(2)
third = float(1) / float(3)
count = 0
for d in range(2, 12000+1):
if d%1000 == 0:
end, start = time() - start, time()
print d, end
for n in range(1, d):
if gcd(n, d) == 1:
nd = float(n) / float(d)
if (third < nd) and (nd < half):
count += 1
print count