Problem #72 concerns Farey sequences. The question reads:
Project Euler Problem 72: Counting 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 there are 21 elements in this set.
How many elements would be contained in the set of reduced proper fractions for d ≤ 1,000,000?
With a bit of knowledge about number theory, it is not too difficult to find a reasonable solution to this problem. Here is my solution:
Solution #1: Brute Force Approach
We can observe that a common fraction n/d is only proper if gcd(n,d) = 1. Thus, for a fixed value of d, only values of n such that 1<=n<d and gcd(n,d) = 1 will form valid common fractions. Thus, the number of common fractions with denominator d is phi(d), or Euler’s Totient Function applied at d. Thus, it suffices to find the sum of phi(d) for 2<=d<=1,000,000. This problem is equivalent to Problem #70, but less computationally intensive. Here is an implementation of this solution in Python 2.7. It is roughly the same as the solution for Problem #70.
'''
Author: Walker Kroubalkian
Semi-Dynamic Approach to Project Euler Problem #72
'''
import time
from math import sqrt
def projectEulerProblemSeventyTwo(n):
totients = [1,1]
for x in range(2,n+1):
v = -1
if(x%2==0):
if(x%4==0):
v = totients[x/2]*2
else:
v = totients[x/2]
else:
c = 3
myRoot = sqrt(x)
while(c<=myRoot):
if(x%c==0):
if(x%(c*c)==0):
v = totients[x/c]*c
else:
v = totients[x/c]*(c-1)
break
c+=2
if(c>myRoot):
v = x-1
totients.append(v)
total = 0
for x in range(2,n+1):
total+=totients[x]
return total
start = time.time()
print projectEulerProblemSeventyTwo(1000000)
print ("--- %s seconds ---" % (time.time()-start))
'''
Prints
303963552391
--- 2.71775197983 seconds ---
for input of n = 1000000.
'''
And with that, we’re done. This solution took over 2.7 seconds to run. Because the problem is essentially equivalent to Problem #70, optimizing this problem is equivalent to optimizing that problem. I may come back to these problems at some point.
Thanks for reading! See you tomorrow.
The Inner Machinations of Walker 