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
     end
     a
   end

   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 > d && 2 * n < d && gcd(n, d) == 1
       end
     end
     answer
   end

   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:
   ?http://en.wikipedia.org/wiki/Euclidean_algorithm. 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.”

   …mrt

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
      Else
         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
      Else
         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.

   …mrt

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