Loading...
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)
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!
Posted by James Bridge | March 17, 2012, 1:07 PMThe 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.
Posted by Mike | March 18, 2012, 4:51 PM