Problem 71
既約分数をn/dとしたとき、d ≤ 1000000の既約分数を大きさの昇順に並べたとき、3/7のすぐ左の分数の分子を求めよ。
http://projecteuler.net/index.php?section=problems&id=71
dは1000000より6小さい数から上になります。なぜなら、そうでない分数p/qがあったとすると、
(p + 3) / (q + 7)
がp/qと3/7にあるからです。
from fractions import FractionN = 10 ** 6
def nearest(x, y):
return x if x[0] <= y[0] else yf = reduce(nearest, map(lambda f: (Fraction(3, 7) - f, f),
map(lambda d: Fraction((d * 3 - 1) / 7, d),
range(N - 6, N + 1))))
print f[1].numerator
