     (7 votes, average: 5.00 out of 5) Loading...

Project Euler 73 Solution 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

Discussion

2 Responses to “Project Euler 73 Solution”

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

• 