Project Euler Problem 73
You are on the Home/Other Tutorials/Project Euler/Problem 73 page
Google
Web This Site

Project Euler - Problem 73

More about Project Euler.

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