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

Project Euler Solutions

Project Euler 71 Solution

Project Euler 71 Solution

Project Euler 71: Listing reduced proper fractions in ascending order of size.


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 2/5 is the fraction immediately to the left of 3/7.

By listing the set of reduced proper fractions for d ≤ 1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7.

Analysis

The answer will always be very close to 3/7*limit. In this case 3/7*1000000 = 428571

Project Euler 71 Solution

Runs < 0.001 seconds in Python 2.7.
download arrowUse this link to get the Project Euler 71 Solution Python 2.7 source.

Afterthoughts

    No afterthoughts yet.
Project Euler 71 Solution last updated

Discussion

No comments yet.

Post a comment