Python Implementation of Problem 73

View source code here on GitHub!

Includes

Problem Solution

Project Euler Problem 73

The biggest problem with this was remembering how to do groupwise()

Revision 1:

By making the boundary conditions better-defined, I was able to shave off a few seconds

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 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?

python.src.p0073.main() → int
 1"""
 2Project Euler Problem 73
 3
 4The biggest problem with this was remembering how to do groupwise()
 5
 6Revision 1:
 7
 8By making the boundary conditions better-defined, I was able to shave off a few seconds
 9
10Problem:
11
12Consider the fraction, n/d, where n and d are positive integers. If n<d and
13HCF(n,d)=1, it is called a reduced proper fraction.
14
15If we list the set of reduced proper fractions for d ≤ 8 in ascending order of
16size, we get:
17
181/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,
193/4, 4/5, 5/6, 6/7, 7/8
20
21It can be seen that there are 3 fractions between 1/3 and 1/2.
22
23How many fractions lie between 1/3 and 1/2 in the sorted set of reduced proper
24fractions for d ≤ 12,000?
25"""
26from fractions import Fraction
27from typing import Set, Tuple
28
29
30def main() -> int:
31    seen: Set[Tuple[int, int]] = set()
32    for x in range(2, 12001):
33        for y in range(x // 3 + 1, (x + 1) // 2):
34            f = Fraction(y, x)
35            seen.add((f.numerator, f.denominator))
36    return len(seen)

Tags: fraction, gcd, stern-brocot-tree