Python Implementation of Problem 72
View source code here on GitHub!
Includes
Problem Solution
Project Euler Problem 72
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 21 elements in this set. How many elements would be contained in the set of reduced proper fractions for d <= 1000000?
1"""
2Project Euler Problem 72
3
4Problem:
5
6Consider the fraction, n / d, where n and d are positive integers. If n < d and HCF(n,d)=1, it is
7called a reduced proper fraction.
8
9If we list the set of reduced proper fractions for d <= 8 in ascending order of size, we get:
10
11(1 / 8), (1 / 7), (1 / 6), (1 / 5), (1 / 4), (2 / 7), (1 / 3), (3 / 8), (2 / 5), (3 / 7), (1 / 2),
12(4 / 7), (3 / 5), (5 / 8), (2 / 3), (5 / 7), (3 / 4), (4 / 5), (5 / 6), (6 / 7), (7 / 8)
13
14It can be seen that there are 21 elements in this set.
15How many elements would be contained in the set of reduced proper fractions for d <= 1000000?
16"""
17from .lib.primes import totient
18
19
20def main() -> int:
21 return sum(totient(n) for n in range(2, 1000001))