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