Problem #73 concerns Farey Sequences. The problem reads:
Project Euler Problem 73: Counting fractions in a range
Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.
If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:
1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8
It can be seen that there are 3 fractions between 1/3 and 1/2.
How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper fractions for d ≤ 12,000?
My solution to this problem is quite bad. Here is my solution:
Solution #1: Brute Force Approach
It is easy to estimate that the number of fractions with denominator d in this range is roughly phi(d)/6. However, determining the exact value requires some messy casework that I would rather avoid. Thus, I opted to use brute force on this problem. I simply iterated through all of the possible denominators less than or equal to 12,000, and then I iterated through all of the numerators within the range for each possible denominator. I used the Euclidean Algorithm to count the number of numerators which were relatively prime to the denominator. Here is an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
Euclidean Algorithm Approach to Project Euler Problem #73
'''
import time
def gcd(a,b):
if(min(a,b)==0):
return max(a,b)
if(a>b):
return gcd(b,a%b)
return gcd(a,b%a)
def projectEulerProblemSeventyThree(n):
total = 0
for x in range(2,n+1):
c = int(x/3)
while(c*3<=x):
c+=1
while(c*2<x):
if(gcd(c,x)==1):
total+=1
c+=1
return total
start = time.time()
print projectEulerProblemSeventyThree(12000)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
7295372
--- 20.5218679905 seconds ---
for input of n = 12000.
'''
And with that, we’re done. This solution took over 20 seconds to run. It could probably be greatly optimized by calculating the totient of each value and then using some casework depending on if the divisor is divisible by 2 or 3 or both. I may come back to implement this more efficient solution at some point.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 