Problem #71 concerns Farey Sequences. The question reads:
Project Euler Problem 71: Ordered fractions
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 2/5 is the fraction immediately to the left of 3/7.
By listing the set of reduced proper fractions for d ≤ 1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7.
With some knowledge of Farey Sequences, this problem can be solved very efficiently. Here is my solution:
Solution #1: Farey Sequence Approach
It is well known that if n/d is the fraction that immediately precedes a/b in a term of the Farey Sequence, then d*a-b*n = 1. Thus, it suffices to find the maximum value of d less than or equal to 1,000,000 such that d*3 leaves a remainder of 1 when divided by 7. At this point, the numerator can be calculated from that value of d. Here is an implementation of this approach in Python 2.7:
'''
Author: Walker Kroubalkian
Brute Force Approach to Project Euler Problem #71
'''
import time
def projectEulerProblemSeventyOne(d,a,b):
c = d
while(c*a%b!=1):
c-=1
return (c*a-1)/b
start = time.time()
print projectEulerProblemSeventyOne(1000000, 3, 7)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
428570
--- 9.77516174316e-06 seconds ---
for input of d = 1000000, a = 3, b = 7.
'''
And with that, we’re done. This solution could be improved in the general case by first determining the modular inverse of a mod b. However, for values of d as small as 1,000,000, this optimization was not necessary.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 