Euler Problem 73

Euler Problem 73 asks:

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?

Here is my code. It uses the same GCD2() function as Problem 75. Takes about 7 seconds.

   Const Min   As Double = 1 / 3
   Const Max   As Double = 1 / 2
   Dim TEMP    As Double
   Dim n       As Long
   Dim d       As Long
   Dim Answer  As Long
   Dim T       As Single
   Dim IsTest  As Boolean
   Dim Top     As Long
   T = Timer
   IsTest = False
   If IsTest Then
      Top = 8
      Top = 10000
   End If
   For d = 2 To Top
      For n = 1 To d – 1
         TEMP = n / d
         If TEMP GT Min And TEMP LT Max Then
            If GCD2(d, n) = 1 Then
               Answer = Answer + 1
            End If
         End If
      Next n
   Next d
   Debug.Print Answer; ”  Time:”, Timer – T
End Sub

Mike W…hope this helps. It has the usual angle bracket substitutions.


Posted in Uncategorized

4 thoughts on “Euler Problem 73

  1. My clunky fraction-reduction code was wrong. I should have had the brain to look up the GCD algorithm, it’s only been around since Euclid, for goodness’ sake.

    That got me solved, albeit slowly (117sec).

    I got to this:

    def gcd(a, b)
      until b == 0 do
        b, a = a % b, b

    def reduced_proper_fraction_count(max_d = 2)
      answer = 0
      5.upto(max_d) do |d|
        (d/3).upto(d/2) do |n|
          answer += 1 if 3 * n &gt; d &amp;&amp; 2 * n &lt; d &amp;&amp; gcd(n, d) == 1

    puts reduced_proper_fraction_count(10_000)

    which ran in a touch under 2 minutes.

    Once I got to the discussion, there were a couple of solutions that I translated, one of which was 7 times faster (it’s on p4, by “danzat” dated 19 May 2008 03:06 pm). I have a feeling that I’ll somehow be just a tiny bit smarter if I understand it, although I may need to get one of my Maths PhD-holding colleagues to explain it to me!

  2. Michael – you must have a fast machine, your code ran in 8.2 seconds on mine (XL 2007). I thought my code was essentially the same as yours, other than being written as a function, but it took only 6.4 seconds on my machine. Here it is:

    Function p_73(Maxd As Long) As Variant
    Dim i As Long, j As Long, ResA(1 To 1, 1 To 2) As Single

    ResA(1, 2) = Timer
    For i = 5 To Maxd
    For j = i / 3 To i / 2
    If j / i GT 1 / 3 Then
    If j / i LT 1 / 2 Then
    If GCD2(i, j) = 1 Then ResA(1, 1) = ResA(1, 1) + 1
    End If
    End If
    Next j
    Next i
    ResA(1, 2) = Timer – ResA(1, 2)
    p_73 = ResA
    End Function

    I used your GCD2 function, which is very neat. When I used worksheetfunction.gcd it ran about 20 x slower in XL2007, which is pretty typical.

    I was interested in the first few comments at the site that the compiled code was taking about as long as the VBA, or even longer.

  3. Hi Doug –

    My laptop continually outperforms my office desktop. Not too much of a surprise there since my desktop is a 3yr old machine ending it’s lease life, and it’s burdened with all the baggage of living in a large corporate IT environment. When I got it, I turned down the corporate laptop because I have this need for speed. ;-) Getting more speed in June with the lease renewal.

    My home laptop is a 2.4 Ghz Intel Core 2 duo, running XP Home and XL2002. I recall that a favorite version of XL for speed was 2002 as commented on by Charles over at Smurf’s blog.

    The really neat thing is that it’s an older MacBook Pro, running Parallels 4 as the Windows emulator. While I couldn’t put my hand on a review Googling just now, I’ve read that Windows runs faster this way than on straight equivalent PC’s. The times I report are from my laptop.

    As for GCD2, in the credit where credit is due department, it’s a translation of the iterative version found here:
    ? Same with GCD1 for recursion. The comment about the classic algorithm (presumably the ws function) is telling: “The original algorithm as described by Euclid treated the problem geometrically, using repeated subtraction rather than mod (remainder). This algorithm is exponentially slower than the division-based algorithm in the worst case, but for small enough input values may provide a benefit on machines without a division instruction.”


  4. In trying to solve Euler Problem 72, which appears to be the same problem, with D = 10^4, and Min = 0, Max = 1, I remembered Mike W’s comment about danzat’s solution for Problem 73. I went and looked it up. This is Problem 73 re-solved using danzat’s recursive function F translated into VBA.

    Sub Problem_073()
       Dim Answer As Long, T As Single
       Dim IsTest As Boolean, MAX As Long
       IsTest = False
       If IsTest Then
          MAX = 8
          MAX = 10 ^ 4
       End If
       T = Timer
       Answer = F(1, 3, 1, 2, MAX)
       Debug.Print Answer; ”  Time:”; Timer – T
    End Sub  
    Function F(a As Long, b As Long, c As Long, d As Long, MAX As Long) As Long
       If b + d GT MAX Then
          F = 0
          F = 1 + F(a, b, a + c, b + d, MAX) + F(a + c, b + d, c, d, MAX)
       End If
    End Function

    This runs in 1.4 seconds on my machine. The F function makes use of a property of two fractions a/b and c/d, with a/b less than c/d. The principal is that (a+c)/(b+d) lies between a/b and c/d. F is first called with a, b, c, d. Call (a+c)/(b+d) as Midpoint1. This corresponds to the 1 added by F. F then looks for the midpoint between a/b and Midpoint1 (and adds 1), and the midpoint between Midpoint1 and c/d (and adds 1). See the recursive calls to F and where a+c and b+d are in each. F keeps recursively dividing the numberline finding midpoints and adding 1 until b+d is at the requiste granularity, and then returns 0. This is the exit condition.

    This implementation doesn’t use GCD at all! Unfortunately it also doesn’t extend to 10^4 granularity as it exhausts the stack. Euler Problem 72 is a Euler Totient problem, and those I don’t comprehend.


Posting code? Use <pre> tags for VBA and <code> tags for inline.

Leave a Reply

Your email address will not be published.