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