(1 votes, average: 5.00 out of 5)

## Project Euler Problem 73 Solution

#### Problem Description

Consider the fraction, n/d, where n and d are positive integers. If n<d and GCD(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 ≤12,000?

Note: The upper limit has been changed recently.

#### Analysis

Simple approach to calculate the number of reduced fractions between 1/3 and 1/2. There are some implementations using the Farey sequence to speed up the search, but didn’t see the need for this problem.

#### Solution

Runs < 35 seconds in Python.

```from Euler import gcd   L = 12000+1 c = 0 for n in range(5, L): for k in range(n/3 + 1, (n-1)/2 + 1): if gcd(n,k) == 1: c+=1   print "Answer to PE73 =", c```

## Discussion

### 3 Responses to “Project Euler Problem 73 Solution”

1. The solution posted here takes several minutes on my computer. I have a version that runs significantly faster (at least on my box, and with my – probably crummy – implementation of factorisation and gcd):

def p73(limit = 12000, ln = 1, ld = 3, un = 1, ud = 3):
from math import floor, ceil
from primes import factorise

c = 0
for d in xrange(limit, 1, -1):
upperN = int(ceil((d*un)/ud)) #the lowest n such that n/d > un/ud
lowerN = int(floor((d*ln)/ld)) #the highest n such that n/d < ln/ld
sieve = [True for x in xrange(upperN)]
sieve[0] = False
factors = factorise(d)
for factor in factors:
for power in xrange(factor, upperN, factor):
sieve[power] = False
c += sum(sieve[lowerN + 1:])
return c

According to my PC it takes only 3.7 seconds.

Posted by Innominate | October 26, 2011, 9:13 AM
2. I have a solution written in C, doing what seems to be exactly the same as your python program. I get a count of 7321831, which gets an X from the Euler site.