Python Implementation of Problem 71
View source code here on GitHub!
Includes
Problem Solution
Project Euler Problem 71
This ended up being mostly a filtering problem. Getting the considered set small enough to run in a reasonable time took a bit. The actual problem is easy
Problem:
Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(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.
1"""
2Project Euler Problem 71
3
4This ended up being mostly a filtering problem. Getting the considered set
5small enough to run in a reasonable time took a bit. The actual problem is easy
6
7Problem:
8
9Consider the fraction, n/d, where n and d are positive integers. If n<d and
10HCF(n,d)=1, it is called a reduced proper fraction.
11
12If we list the set of reduced proper fractions for d ≤ 8 in ascending order of
13size, we get:
14
151/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,
163/4, 4/5, 5/6, 6/7, 7/8
17
18It can be seen that 2/5 is the fraction immediately to the left of 3/7.
19
20By listing the set of reduced proper fractions for d ≤ 1,000,000 in ascending
21order of size, find the numerator of the fraction immediately to the left of
223/7.
23"""
24from fractions import Fraction
25
26
27def main() -> int:
28 return max(
29 Fraction(x, y)
30 for y in range(1, 1_000_000)
31 for x in range((y - 1) * 3 // 7, y * 3 // 7)
32 ).numerator