## Project Euler 73: How many fractions lie between two points in a sorted set of reduced proper fractions

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

Update: A much improved version that removes the gcd() function and uses a list to speed up the program.

#### Project Euler 73 Solution

Runs < 0.017 seconds in Python 2.7.Use this link to get the Project Euler 73 Solution Python 2.7 source.

#### Afterthoughts

`n1`,`d1`and`n2`,`d2`represent the boundaries`n1`/`d1`and`n2`/`d2`. The default is set to the problem parameters 1/3 and 1/2 respectively. You could change this to d ≤ 8: 3/8 and 5/6 by calling the function with those boundaries as:`p(8,3,8,5,6)`

*Project Euler 73 Solution last updated*

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.

Any suggestions gratefully received!

The range function in Python creates a range up to but not including the upper limit. For example:

>>> range(1, 11)

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

This is, most likely, the source of the confusion. The answer is a seven-digit number starting with 7, so you’re in the right neighborhood.