﻿ Project Euler Problem 73
You are on the Home/Other Tutorials/Project Euler/Problem 73 page

Web This Site

Project Euler - Problem 73

Problem description

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?

Solution

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```