39 lines
1.2 KiB
Python
39 lines
1.2 KiB
Python
#!/usr/bin/env python3
|
|
|
|
# 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?
|
|
|
|
from math import gcd
|
|
|
|
from projecteuler import timing
|
|
|
|
|
|
@timing
|
|
def p073():
|
|
count = 0
|
|
|
|
# For each denominator q, we need to find the fractions p/q for which
|
|
# 1/3<p/q<1/2. For the lower limit, if p=q/3, then p/q=1/3, so we take
|
|
# p=q/3+1. For the upper limit, if p=q/2 p/q=1/2, so we take p=(q-1)/2.
|
|
for i in range(2, 12001):
|
|
limit = (i - 1) // 2 + 1
|
|
|
|
for j in range(i//3+1, limit):
|
|
# Increment the counter if the current fraction is reduced.*/
|
|
if gcd(j, i) == 1:
|
|
count = count + 1
|
|
|
|
print('Project Euler, Problem 73')
|
|
print(f'Answer: {count}')
|
|
|
|
|
|
if __name__ == '__main__':
|
|
p073()
|