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.

Problem_073()

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

Else

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

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

Else

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.

…mrt

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:

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!

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:

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.

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

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.

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