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 ≤ 10,000?
I tried a couple of optimizations to try and save time but each gave me an incorrect result. So, I switched to brute force. The code below ran in about 12 seconds.
Function GCD(ByVal a, ByVal b) Do Dim TEMP TEMP = b b = a Mod b a = TEMP Loop Until b = 0 GCD = a End Function Sub Euler073() Dim D As Integer, Ans As Long Dim StartTime As Single: StartTime = Timer For D = 1 To 10000 Dim LowLim As Integer, HighLim As Integer Dim N As Integer For N = 1 To D - 1 If 3 * N > D And 2 * N < D Then Dim aGCD: aGCD = GCD(N, D) If aGCD = 1 Then Ans = Ans + 1 End If End If Next N Next D Debug.Print Ans; Timer - StartTime End Sub