Add-ins:
Excel
PowerPoint

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