// you’re reading...
1 Star2 Stars3 Stars4 Stars5 Stars (7 votes, average: 5.00 out of 5)
Loading...

Project Euler Solutions

Project Euler 73 Solution

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.
download arrowUse 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.

    Any suggestions gratefully received!

    Posted by James Bridge | March 17, 2012, 1:07 PM
    • 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.

      Posted by Mike | March 18, 2012, 4:51 PM

Post a comment