51 lines
1.5 KiB
Python
51 lines
1.5 KiB
Python
from lib_misc import gcd
|
|
|
|
|
|
def smallest_fraction_with_new_denominator(n, d, d_new):
|
|
return (int(d_new / d * n), d_new)
|
|
|
|
|
|
def euler_071():
|
|
"""
|
|
The idea is to find the the closest fraction to (n, d) for every potential
|
|
new denominator d_new. We do that by extrapolating (n, d) to d_new and
|
|
rounding n_new down. This is what smallest_fraction_with_new_denominator
|
|
does.
|
|
|
|
We can then check if the greatest common divisor for n_new and d_new is
|
|
one. I though it might be necessary to search for the next smallest n_new
|
|
if gcd(n_new, d_new) > 1, but it turned out that this is not actually
|
|
necessary.
|
|
"""
|
|
n = 3
|
|
d = 7
|
|
n_min, d_min = 0, 1
|
|
for d_new in range(950000, 1000000):
|
|
n_new, d_new = smallest_fraction_with_new_denominator(n, d, d_new)
|
|
if d_new == d:
|
|
pass
|
|
elif gcd(n_new, d_new) == 1 and n_new / d_new > n_min / d_min:
|
|
n_min, d_min = n_new, d_new
|
|
return n_min
|
|
|
|
|
|
def euler_071_farey():
|
|
"""
|
|
https://www.cut-the-knot.org/blue/Farey.shtml
|
|
n_min must be located between 2/5 and 3/7 for F_7
|
|
To calculate F_d where d <= 10**6 we continously calculate the
|
|
median between 3/7 and the new fraction.
|
|
"""
|
|
n, d = (3, 7)
|
|
n_D, d_D = (2, 5)
|
|
while d_D + d <= 10**6:
|
|
n_D = n_D + n
|
|
d_D = d_D + d
|
|
return n_D
|
|
|
|
|
|
if __name__ == "__main__":
|
|
print(euler_071_farey())
|
|
print("e071.py: " + str(euler_071()))
|
|
assert(euler_071() == 428570)
|